#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#define N 2000005
map <int, int> pos, note;
int arr[N], mx, cnt, p;
bool can;
long long mod = 1e9 + 9, ans = 1;
vector <int> vc;
int valid(int n, int inputSeq[]){
for (int i = 0;i < n;i++){
if (mx < inputSeq[i]){
mx = inputSeq[i];
p = i;
}
pos[inputSeq[i]] = i;
if (note[inputSeq[i]]) return 0;
note[inputSeq[i]] = 1;
}
for (int i = 0;i < n;i++)
if (inputSeq[i] <= n){
can = 1;
int now = inputSeq[i];
arr[i] = now;
for (int j = i + 1;j < n;j++){
now++;
if (now > n) now = 1;
arr[j] = now;
}
for (int j = 0;j < i;j++){
now++;
if (now > n) now = 1;
arr[j] = now;
}
break;
}
if (!can)
for (int i = 0;i < n;i++)
arr[i] = i + 1;
int ok = 1;
for (int i = 0;i < n;i++)
if (inputSeq[i] <= n && inputSeq[i] != arr[i])
ok = 0;
return ok;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
if (!valid(n, gondolaSeq)) return 0;
for (int i = 0;i < n;i++)
if (gondolaSeq[i] > n)
vc.push_back(gondolaSeq[i]);
for (int i = n + 1;i <= mx;i++){
if (!note[i]) {
replacementSeq[i - n - 1] = arr[p];
arr[p] = i;
}
else replacementSeq[i - n - 1] = arr[pos[i]];
}
return mx - n;
}
long long gg(long long x, int y){
long long s = 1;
while (y){
if (y % 2) s = (s * x) % mod;
x = (1ll * x * x) % mod;
y /= 2;
}
return s;
}
int countReplacement(int n, int inputSeq[]){
if (!valid(n, inputSeq)) return 0;
if (!can) ans = n;
for (int i = 0;i < n;i++)
if (inputSeq[i] > n)
vc.push_back(inputSeq[i]);
sort(vc.begin(), vc.end());
reverse(vc.begin(), vc.end());
int bef = n;
while (!vc.empty()){
ans = (ans * gg(vc.size(), vc.back() - bef - 1)) % mod;
bef = vc.back();
vc.pop_back();
}
return ans;
}
