#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
#include "gondola.h"
int valid(int n, int inputSeq[]) {
int ind = -1, x = -1;
for(int i = 0; i < n; i++) {
if(inputSeq[i] <= n) {
ind = i;
x = inputSeq[i];
break;
}
}
for(int i = ind + 1; i < n; i++) {
if(inputSeq[i] <= n and (x + i - ind - 1) % n + 1 != inputSeq[i])
return 0;
}
set < int > s;
for(int i = 0; i < n; i++)
s.insert(inputSeq[i]);
return s.size() == n;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int ind = 1;
for(int i = 0; i < n; i++) {
if(gondolaSeq[i] <= n) {
ind = (gondolaSeq[i] - 1 - i + n) % n + 1;
break;
}
}
vector < ii > v;
for(int i = 0; i < n; i++) {
v.push_back(ii(gondolaSeq[i], (ind + i - 1) % n + 1));
}
sort(v.begin(), v.end());
int nxt = n + 1, sz = 0;
foreach(it, v) {
int x = it -> first;
int i = it -> second;
while(nxt <= x) {
replacementSeq[sz++] = i;
i = nxt;
nxt++;
}
}
return sz;
}
//----------------------
const int mod = 1e9 + 9;
int countReplacement(int n, int inputSeq[]) {
if(!valid(n, inputSeq))
return 0;
int ans = 1;
int mx = *max_element(inputSeq, inputSeq + n);
set < int > s;
for(int i = 0; i < n; i++)
if(inputSeq[i] >= n)
s.insert(inputSeq[i]);
for(int i = n + 1; i <= mx; i++) {
if(s.count(i)) {
s.erase(i);
continue;
}
ans = (ll) ans * s.size() % mod;
}
//if(*min_element(inputSeq, inputSeq + n) > n)
// ans = (ll) ans * n % mod;
return ans;
}
