#include "gondola.h"
#include <algorithm>
#include <vector>
#define MOD 1000000009
using namespace std;
typedef pair <int,int> ppair;
vector <ppair> A;
int Check[250001], L;
long long Num, B[101];
int valid(int n, int inputSeq[])
{
int i, X=-1, Y;
for(i=0 ; i<n ; i++)
{
if(Check[inputSeq[i]])
return 0;
Check[inputSeq[i]]=1;
if(inputSeq[i]<=n)
{
X=i;
Y=inputSeq[i];
}
}
if(X==-1)
return 1;
for(i=X+1 ; i<n ; i++)
{
Y++;
if(Y>n)
Y=1;
if(inputSeq[i]<=n && inputSeq[i]!=Y)
return 0;
}
for(i=0 ; i<=X-1 ; i++)
{
Y++;
if(Y>n)
Y=1;
if(inputSeq[i]<=n && inputSeq[i]!=Y)
return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int i, X=-1, Y, Size;
for(i=0 ; i<n ; i++)
if(gondolaSeq[i]<=n)
{
X=i;
Y=gondolaSeq[i];
break;
}
if(X==-1)
for(i=0 ; i<n ; i++)
A.push_back(make_pair(gondolaSeq[i],i+1));
else
{
for(i=X+1 ; i<n ; i++)
{
Y++;
if(Y>n)
Y=1;
if(gondolaSeq[i]>n)
A.push_back(make_pair(gondolaSeq[i],Y));
}
for(i=0 ; i<=X-1 ; i++)
{
Y++;
if(Y>n)
Y=1;
if(gondolaSeq[i]>n)
A.push_back(make_pair(gondolaSeq[i],Y));
}
}
sort(A.begin(),A.end());
X=0;
Y=n+1;
Size=A.size();
while(X<Size)
{
replacementSeq[L++]=A[X].second;
A[X].second=Y;
Y++;
if(A[X].first==A[X].second)
X++;
}
return L;
}
long long Multi(int X, int Y)
{
int i, Z;
long long Temp;
B[0]=Y;
for(i=1 ; i<=50 ; i++)
{
B[i]=B[i-1]*B[i-1];
B[i]%=MOD;
}
Temp=1;
Z=0;
while(X)
{
if(X&1)
Temp*=B[Z];
Z++;
X>>=1;
Temp%=MOD;
}
return Temp;
}
int countReplacement(int n, int inputSeq[])
{
int i, j, X=-1, Y;
for(i=0 ; i<n ; i++)
{
A.push_back(make_pair(inputSeq[i],0));
if(inputSeq[i]<=n)
{
X=i;
Y=inputSeq[i];
}
}
sort(A.begin(),A.end());
j=A.size();
for(i=1 ; i<j ; i++)
if(A[i].first==A[i-1].first)
return 0;
for(i=X+1 ; i<n ; i++)
{
Y++;
if(Y>n)
Y=1;
if(inputSeq[i]<=n && inputSeq[i]!=Y)
return 0;
}
for(i=0 ; i<=X-1 ; i++)
{
Y++;
if(Y>n)
Y=1;
if(inputSeq[i]<=n && inputSeq[i]!=Y)
return 0;
}
A.clear();
A.push_back(make_pair(n,0));
X=1;
for(i=0 ; i<n ; i++)
{
if(inputSeq[i]>n)
A.push_back(make_pair(inputSeq[i],0));
else
X=0;
}
if(X)
Num=n;
else
Num=1;
sort(A.begin(),A.end());
j=A.size();
for(i=1 ; i<j ; i++)
{
Num*=Multi(A[i].first-A[i-1].first-1,j-i);
Num%=MOD;
}
return Num;
}
