#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+n)%n;
else if(offset!=(inputSeq[i]-i+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 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);
int num=0;
for(int i=mx;i>n;--i){
if(changed.find(i)!=changed.end())++num;
else{
ans=(ans*num)%mod;
}
}
return (int)ans;
}
