#include<bits/stdc++.h>
#include"gondola.h"
using namespace std;
#define ii pair<int,int>
#define fi first
#define se second
const int mod=1e9+9;
int poww(int n,int m)
{
int res=n,ans=1;
while(m)
{
if(m&1) ans=(long long)ans*res%mod;
res=(long long)res*res%mod,m/=2;
}
return ans;
}
int valid(int n,int inputSeq[])
{
int uni=-1;
bool ck=true;
map<int,int> mp;
for(int i=0;i<n;i++)
{
if(mp[inputSeq[i]]) return 0;
if(inputSeq[i]<=n)
{
int res=(inputSeq[i]-(i+1)+n)%n;
if(uni==-1) uni=res;
else if(res!=uni) return 0;
}
mp[inputSeq[i]]=true;
}
return 1;
}
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
int uni=-1,ans=0,prv=n;
for(int i=0;i<n;i++) if(gondolaSeq[i]<=n&&uni==-1) uni=(gondolaSeq[i]-(i+1)+n)%n;
if(uni==-1) uni=0;
vector<ii> val(n);
for(int i=0;i<n;i++) val[i]={gondolaSeq[i],i};
sort(val.begin(),val.end());
for(int i=0;i<n;i++) if(val[i].fi>n)
{
int pre=(val[i].se+uni)%n+1;
replacementSeq[ans++]=pre;
for(int j=prv+1;j<val[i].fi;j++) replacementSeq[ans++]=j;
prv=val[i].fi;
}
return ans;
}
int countReplacement(int n,int inputSeq[])
{
int uni=-1,ans=1,prv=n;
bool ck=true,eu=false;
map<int,int> mp;
for(int i=0;i<n;i++)
{
if(mp[inputSeq[i]]) return 0;
if(inputSeq[i]<=n)
{
int res=(inputSeq[i]-(i+1)+n)%n;
if(uni==-1) uni=res,eu=true;
else if(res!=uni) return 0;
}
mp[inputSeq[i]]=true;
}
if(uni==-1) uni=0;
vector<ii> val(n);
for(int i=0;i<n;i++) val[i]={inputSeq[i],i};
sort(val.begin(),val.end());
for(int i=0;i<n;i++) if(val[i].fi>n) ans=(long long)ans*poww(n-i,val[i].fi-prv-1)%mod,prv=val[i].fi;
if(!eu) ans=(long long)ans*n%mod;
return ans;
}
