#include "gondola.h"
#include<map>
using namespace std;
map<int,int>fre;
int valid(int n, int inputSeq[])
{
int offset=-1,val,off2;
fre.clear();
for(int i=1; i<=n; i++)
{
val=inputSeq[i-1];
fre[val]++;
if(fre[val]>=2)
{
return 0;
}
if(val<=0)
{
return 0;
}
if(val<=n && offset==-1)
{
offset=(i-val+n)%n;
}
else if(val<=n)
{
off2=(i-val+n)%n;
if(off2!=offset)
{
return 0;
}
}
}
return 1;
}
//----------------------
int v[100005];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int valmax=0,val,pozmax=0,offset=-1;
fre.clear();
for(int i=1; i<=n; i++)
{
val=gondolaSeq[i-1];
fre[val]=i;
valmax=max(valmax,val);
if(val<=n && offset==-1)
{
offset=(i-val+n)%n;
}
if(val==valmax)
{
pozmax=i;
}
}
for(int i=1; i<=n; i++)
{
v[i]=(i-offset+n-1)%n+1;
}
for(int i=n+1; i<=valmax; i++)
{
if(fre[i]==0)
{
replacementSeq[i-n-1]=v[pozmax];
v[pozmax]=i;
}
else
{
replacementSeq[i-n-1]=v[fre[i]];
v[fre[i]]=i;
}
}
return valmax-n;
}
//----------------------
int spar[500005];
long long mod=1e9+9;
long long lgpow(long long a,long long exp)
{
long long prod=1;
while(exp)
{
if(exp%2==1)
{
prod=(a*prod)%mod;
}
a=(a*a)%mod;
exp=exp/2;
}
return prod;
}
int countReplacement(int n, int inputSeq[])
{
int valmax=0,val,pozmax=0,offset=-1;
if(valid(n,inputSeq)==0)
{
return 0;
}
fre.clear();
int cnt=0;
for(int i=1; i<=n; i++)
{
val=inputSeq[i-1];
valmax=max(valmax,val);
if(val<=n && offset==-1)
{
offset=(i-val+n)%n;
}
if(val>n)
{
spar[n+1]++;
spar[val]--;
fre[val]=i;
cnt++;
}
}
long long prod=1;
if(offset==-1)
{
prod=n;
}
fre[n]=0;
for(auto it=fre.begin();it!=fre.end();it++)
{
if(it->first!=n)
{
auto it2=it;
it2--;
prod=(prod*lgpow(cnt,it->first-it2->first-1))%mod;
cnt--;
}
}
return prod%mod;
}
