#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000009
int valid(int n,int inputSeq[]){
int offset=-1;
set<int> s;
for(int i=0;i<n;++i){
if(s.find(inputSeq[i])!=s.end())return 0;
s.insert(inputSeq[i]);
if(inputSeq[i]<=n){
if(offset==-1)offset=(inputSeq[i]-i-1+n)%n;
else if(offset!=(inputSeq[i]-i-1+n)%n)return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
set<int> changed;
map<int,int> pos;
int offset=0,dummy=0,cur=0;
int mx=0;
for(int i=0;i<n;++i){
if(gondolaSeq[i]<=n)offset=(gondolaSeq[i]-1-i+n)%n;
else{
changed.insert(gondolaSeq[i]);
if(gondolaSeq[i]>gondolaSeq[dummy])dummy=i;
}
mx=max(mx,gondolaSeq[i]);
}
for(int i=0;i<n;++i){
if(gondolaSeq[i]>n){
pos[gondolaSeq[i]]=((i+offset)%n)+1;
}
}
cur=(dummy+offset)%n+1;
int ori=cur;
for(int i=n+1;i<=mx;++i){
if(changed.find(i)==changed.end()||pos[i]==ori){
replacementSeq[i-n-1]=cur;
cur=i;
}
else{
replacementSeq[i-n-1]=pos[i];
}
}
return mx-n;
}
//----------------------
int fp(int x,int a){
if(a==0)return 1;
int t=fp(x,a/2);
long long r=((long long)t*t)%mod;
if(a%2)r=(r*x)%mod;
return (int)r;
}
int countReplacement(int n, int inputSeq[]){
set<int> changed;
int mx=0;
for(int i=0;i<n;++i){
if(inputSeq[i]>n){
changed.insert(inputSeq[i]);
mx=max(mx,inputSeq[i]);
}
}
long long ans=valid(n,inputSeq);
if(changed.size()==0)return (int)ans;
int num=1;
int pv=*(--changed.end());
changed.erase(--changed.end());
while(!changed.empty()){
int x=*(--changed.end());
changed.erase(--changed.end());
ans=(ans*fp(num,pv-x-1))%mod;
pv=x;
++num;
}
ans=(ans*fp(num,pv-n-1))%mod;
return (int)ans;
}
