#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
long long binpow(long long a, long long b, long long m) {
a %= m;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int valid(int n, int inputSeq[]){
bool seen[250001];
fill_n(seen, 250001, 0);
int anc = 0;
for(int i = 0; i<n; i++){
if(inputSeq[i] <= n){
anc = i;
break;
}
}
int canc = inputSeq[anc];
for(int i = 0; i<n; i++){
if(inputSeq[i] > n){
if(seen[inputSeq[i]]){
return 0;
}
seen[inputSeq[i]] = 1;
}
else{
if(inputSeq[i] != canc){
return 0;
}
}
canc++;
if(canc > n){
canc -= n;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int high[250001]; // position of high element if exists
fill_n(high, 250001, -1);
int anc = 0;
for(int i = 0; i<n; i++){
if(gondolaSeq[i] <= n){
anc = i;
break;
}
}
for(int i = 0; i<n; i++){
if(gondolaSeq[i] > n){
high[gondolaSeq[i]] = i;
}
}
int l = 0;
int lasth = n;
for(int i = n; i<250001; i++){
if(high[i] != -1){
//get initial value at high[i]
int init = (high[i]+n)-anc;
init += gondolaSeq[anc];
while(init > n){
init -= n;
}
replacementSeq[l] = init;
l++;
lasth++;
while(lasth < i){
replacementSeq[l] = lasth;
l++;
lasth++;
}
}
}
return l;
}
int countReplacement(int n, int inputSeq[]){
// int high[1000000001]; // position of high element if exists
// fill_n(high, 1000000001, -1);
set<long long> high;
long long bcount = 0;
int ok = 1;
int should = -1;
for(int i = 0; i<n; i++){
if(high.find(inputSeq[i]) != high.end()){
ok = 0;
}
high.insert(inputSeq[i]);
if(inputSeq[i] > n){
bcount++;
}
else{
if(should == -1){
should = inputSeq[i];
}
else{
if(inputSeq[i] != should){
ok = 0;
}
}
}
if(should != -1){
should++;
if(should > n){
should -= n;
}
}
}
if(!ok) return ok;
long long mod = 1000000009;
long long ans = 1;
if(bcount == n){ //NEW
ans *= n; //NEW
} //NEW
int last = n;
for(auto v : high){
if(v <= n) continue;
long long pow = v-last-1;
ans = (ans*binpow(bcount, pow, mod))%mod;
last = v;
bcount--;
}
// for(int i = n+1; i<250001; i++){
// if(high[i] == -1){
// ans = (ans*(max((long long)1, bcount)))%mod;
// }
// else{
// bcount--;
// }
// }
return (int)ans;
}
// int main(){
// int t;
// cin>>t;
// if(t > 6){
// int n;
// cin>>n;
// int v[n];
// for(int i = 0; i<n; i++){
// cin>>v[i];
// }
// int l = countReplacement(n, v);
// cout<<l<<"\n";
// }
// }
