#include "gondola.h"
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int nmax=100005;
const long long mod=1000*1000*1000+9;
map<int,int> ap;
int v[nmax];
int i,act;
void permuta(int a[],int b[],int n)
{
int offset=0;
for(int i=0;i<n;i++)
if(a[i]<=n)
offset=i+1-a[i];
for(int i=0;i<n;i++)
b[i]=a[(i+offset+n)%n];
}
int valid(int n, int inputSeq[])
{
permuta(inputSeq,v,n);
for(int i=0;i<n;i++)
{
if(v[i]<=n&&v[i]!=i+1)
return 0;
if(ap[v[i]]) return 0;
ap[v[i]]=1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int l=0;
permuta(gondolaSeq,v,n);
int mx=0;
for(i=0;i<n;i++)
{
ap[v[i]]=i+1;
mx=max(mx,v[i]);
}
act=n;
for(i=n+1;i<=mx;i++)
if(ap[i])
{
replacementSeq[l++]=ap[i];
act++;
while(act<i)
{
replacementSeq[l++]=act;
act++;
}
}
return l;
}
//----------------------
long long expo(long long A,int B)
{
long long ret=1,p2=A;
for(int p=0;p<=30;p++)
{
if(((1<<p)&B))
ret=(1LL*ret*p2)%mod;
p2=(1LL*p2*p2)%mod;
}
return ret;
}
int countReplacement(int n, int inputSeq[])
{
long long f=0,ans=1;
if(!valid(n,inputSeq)) return 0;
bool ordered=1;
for(int i=1;i<=n;i++)
if(ap[i])
ordered=0;
sort(inputSeq,inputSeq+n);
for(i=n-2;i>=0;i--)
if(inputSeq[i]>n||inputSeq[i+1]>n)
{
f=n-1-i;if(inputSeq[i]<n) inputSeq[i]=n;
ans=(1LL*ans*expo(f,inputSeq[i+1]-inputSeq[i]-1))%mod;
}
if(ordered)
{
f=n;
ans=(1LL*ans*expo(f,inputSeq[0]-n-1))%mod;
f=n;
ans=(1LL*ans*f)%mod;
}
return ans;
}
