#include "bits/stdc++.h"
// #include "grader.h"
#include "gondola.h"
using namespace std;
#define N 500005
const int M = 1e9 + 9;
int a[N], b[N], vis[N], f[N], D[N];
set <long long> g ={}, h = {}, gg;
vector <int> v;
bool check(int x,int ch) {
if(!ch) {
if((int)g.size() != x ||(int)h.size() > 1) return 0;
if((int)h.size() == 0) return 1;
}
int val = *h.begin();
for(int i = 1; i <= x; i++) {
int pos = i;
if(i <= val) pos += x;
b[pos - val - 1] = i;
}
for(int i = 0; i < x; i++) {
if(a[i] > x) continue;
if(a[i] != b[i]) return 0;
}
return 1;
}
int valid(int n, int inputSeq[]) {
for(int i = 0; i < n; i++) {
a[i] = inputSeq[i];
g.insert(a[i]);
if(a[i] < n) {
if(a[i] >= i + 1) h.insert(a[i] - (i + 1));
else h.insert((n + a[i]) - (i + 1));
}
}
return check(n, 0);
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
for(int i = 0; i < n; i++) {
a[i] = gondolaSeq[i];
b[i] = i + 1;
g.insert(a[i]);
vis[a[i]] = 1;
if(a[i] < n) {
if(a[i] >= i + 1) h.insert(a[i] - (i + 1));
else h.insert((n + a[i]) - (i + 1));
}
}
set <pair <int,int>> st;
int x = check(n, 1);
int sz = 0, ls = n + 1;
for(int i = 0; i < n; i++) {
assert(b[i] >= 1 && b[i] <= n);
if(a[i] != b[i]) st.insert({a[i], b[i]});
}
while(!st.empty()){
auto ii = *st.begin();
int ap = ii.second, ak = ii.first;
replacementSeq[sz++] = ap;
while(ls != ak) {
replacementSeq[sz++] = ls++;
}
ls++;
st.erase(st.begin());
}
return sz;
}
long long calc(long long x,long long y){
if(!y) return 1;
long long F = calc(x, y / 2)%M;
return F * F % M * (y % 2 != 0 ? x : 1) % M;
}
int countReplacement(int n, int inputSeq[])
{
for(int i = 0; i < n; i++) {
a[i] = inputSeq[i];
g.insert(a[i]);
if(a[i] <= n) {
if(a[i] >= i + 1) h.insert(a[i] - (i + 1));
else h.insert((n + a[i]) - (i + 1));
}
else gg.insert(a[i]);
}
if(!check(n,0)) return 0;
long long d = (int)gg.size(), ans = 1;
if(d == 0) return 1;
if(d == n) ans = n;
long long ls = n, i = 0;
while(!gg.empty()) {
int vl = *gg.begin();
ans = (long long)1 * ans % M * calc(d - i, vl - ls - 1) % M;
ls = vl;
i++;
gg.erase(gg.begin());
}
int answer = ans % M;
return answer;
}
