#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int M = 250005;
const int mod = 1000000009;
int valid(int n, int seq[])
{
vector<int> vis(M);
for (int i = 0; i < n; i++)
{
if (vis[seq[i]]) return 0;
vis[seq[i]] = true;
}
int cur = -1;
for (int i = 0; i < n; i++) seq[i]--;
for (int i = 0; i < n; i++)
{
if (seq[i] < n)
{
cur = i;
break;
}
}
if (cur == -1) return 1;
int val = seq[cur];
for (int i = cur + 1; i < n; i++)
{
val++;
val %= n;
if (seq[i] < n && seq[i] != val) return 0;
}
return 1;
}
//----------------------
int replacement(int n, int seq[], int seq2[])
{
vector<int> to(M, -1);
int biggest = -1;
int cbig = -1;
for (int i = 0; i < n; i++)
{
seq[i]--;
to[seq[i]] = i;
if (seq[i] > cbig)
{
cbig = seq[i];
biggest = i;
}
}
if (cbig == n - 1) return 0;
int org[M];
for (int i = 0; i < n; i++) org[i] = -1;
for (int i = 0; i < n; i++)
{
if (seq[i] < n)
{
for (int j = 0; j < n; j++)
{
org[j] = ((seq[i] - (i - j)) % n + n) % n;
}
break;
}
}
if (org[0] == -1)
{
for (int i = 0; i < n; i++) org[i] = i;
}
int cur = 0;
for (int cnum = n; cnum <= cbig; cnum++)
{
if (to[cnum] == -1)
{
seq2[cur] = org[biggest] + 1;
org[biggest] = cnum;
} else
{
seq2[cur] = org[to[cnum]] + 1;
org[to[cnum]] = cnum;
}
cur++;
}
return cur++;
}
/*
4
2
10 11
*/
//----------------------
int countReplacement(int n, int seq[])
{
if (!valid(n, seq)) return 0;
set<int> to;
int open = 0;
int cbig = -1;
for (int i = 0; i < n; i++)
{
to.insert(seq[i]);
if (seq[i] >= n) open++;
cbig = max(cbig, seq[i]);
}
bool allBigger = true;
for (int i = 0; i < n; i++) if (seq[i] < n) allBigger = false;
long long res = 1;
if (allBigger) res = n;
for (int cnum = n; cnum <= cbig; cnum++)
{
if (to.find(cnum) == to.end())
{
res *= open;
res %= mod;
} else
{
open--;
}
}
return res;
}
