#include <stdio.h>
#include <assert.h>
#include <algorithm>
#include <unordered_set>
#include "gondola.h"
#define MOD 1000000009
int poz[100010];
std::unordered_set<int>e;
int valid(int n, int inputSeq[])
{
for(int i=0;i<n;++i)
{
if(e.find(inputSeq[i])!=e.end())
return 0;
e.insert(inputSeq[i]);
if(1<=inputSeq[i]&&inputSeq[i]<=n)
poz[inputSeq[i]]=i+1;
}
int dif=-1;
for(int i=1;i<=n;++i)
if(poz[i])
{
int val;
if(i<=poz[i])
val=poz[i]-i;
else
val=poz[i]+n-i;
if(dif==-1)
dif=val;
else if(dif!=val)
return 0;
}
return 1;
}
//----------------------
int ago[100010];
int truevalue(int val,int n)
{
while(val<=0)
val+=n;
return val;
}
int goodshift(int n,int gondolaSeq[])
{
int ls=-1;
for(int i=0;i<n;++i)
if(1<=gondolaSeq[i]&&gondolaSeq[i]<=n)
{
if(gondolaSeq[i]<=i+1)
ls=i+1-gondolaSeq[i];
else
ls=i+1+n-gondolaSeq[i];
break;
}
if(ls==-1)
{
for(int i=0;i<n;++i)
ago[i+1]=gondolaSeq[i];
return 0;
}
for(int i=0;i<n;++i)
ago[truevalue(i+1-ls,n)]=gondolaSeq[i];
return 1;
}
int pozval[250010],valac;
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
goodshift(n,gondolaSeq);
for(int i=1;i<=n;++i)
pozval[ago[i]]=i;
valac=n;
for(int i=1;i<=n;++i)
ago[i]=i;
for(int i=n+1;i<=250000;++i)
{
if(pozval[i]!=0)
{
while(valac<i)
{
replacementSeq[valac-n]=ago[pozval[i]];
++valac;
ago[pozval[i]]=valac;
}
}
}
return valac-n;
}
//----------------------
long long ans=1;
int countReplacement(int n, int inputSeq[])
{
if(valid(n,inputSeq)==0)
return 0;
std::sort(inputSeq,inputSeq+n);
if(inputSeq[0]>n)
ans*=n;
int poz=0;
while(poz<n&&inputSeq[poz]<=n)
++poz;
for(int i=n+1;i<=inputSeq[n-1];++i)
{
if(i==inputSeq[poz])
++poz;
else
{
ans*=(n-poz);
ans%=MOD;
}
}
return ans;
}
