#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int valid(int n, int seq[])
{
map<int,int> mp;
bool ch=true;
int temp=-1;
for(int i=0;i<n;i++)
{
if(seq[i]<=n)
{
if(ch)
{
ch=false;
temp=(seq[i]-i+n)%n;
}
else if((seq[i]-i+n)%n!=temp) return 0;
}
if(mp[seq[i]]) return 0;
else mp[seq[i]]=1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int ma=-1;
for(int i=0;i<n;i++) ma=max(gondolaSeq[i],ma);
int permu=1;
for(int i=0;i<n;i++)
{
if(gondolaSeq[i]<=n)
{
permu=(gondolaSeq[i]-i+n)%n;
}
}
int gondo[250010]={};
for(int i=0;i<n;i++) gondo[gondolaSeq[i]]=(i+n-1+permu)%n+1;
int onpath[250010]={};
for(int i=1;i<=n;i++) onpath[i]=i;
int temp=gondo[ma];
for(int i=n+1;i<=ma;i++)
{
if(gondo[i])
{
replacementSeq[i-n-1]=onpath[gondo[i]];
onpath[gondo[i]]=i;
}
else
{
replacementSeq[i-n-1]=onpath[temp];
onpath[temp]=i;
}
}
return ma-n;
}
//----------------------
ll big=1000000009;
ll expo(int x,int y)
{
if(y==0) return 1ll;
if(y==1) return (long long)x;
if(y&1) return ((((expo(x,y>>1))*(expo(x,y>>1)))%big)*(long long)x)%big;
return ((expo(x,y>>1))*(expo(x,y>>1)))%big;
}
int countReplacement(int n, int inputSeq[])
{
ll res=1;
if(!valid(n,inputSeq)) return 0;
bool ch=false;
int ti[n];
for(int i=0;i<n;i++)
{
ti[i]=inputSeq[i];
if(ti[i]<=n) ch=true;
}
sort(ti,ti+n);
for(int i=n-1;i>=0;i--)
{
if(ti[i]<=n) break;
if(i) res*=expo(n-i,ti[i]-max(ti[i-1],n)-1);
else res*=expo(n,ti[0]-n-1);
res%=big;
}
if(!ch)
{
res*=(long long)n;
res%=big;
}
return (int)res;
}
