#include "gondola.h"
#include <vector>
#include <algorithm>
using namespace std;
int valid(int n, int inputSeq[])
{
//duplication check
vector<int> dupe;
for(int i=0;i<n;i++)
dupe.push_back(inputSeq[i]);
sort(dupe.begin(),dupe.end());
for(int i=0;i<n-1;i++)
if(dupe[i]==dupe[i+1]) return 0;
//rotatable check
int key=-1;
for(int i=0;i<n;i++)
if(inputSeq[i]<=n)
key=i;
if(key==-1) return 1;
for(int i=0;i<n;i++)
{
if(inputSeq[i]>n) continue;
if((inputSeq[i]-inputSeq[key]+n)%n!=(i-key+n)%n) return 0;
//do not have same diff
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
if(!valid(n,gondolaSeq)) return 0;
int key=0;
for(int i=0;i<n;i++)
if(gondolaSeq[i]<=n)
key=i;
vector<int> newSeq;
for(int i=0;i<n;i++)
newSeq.push_back((i+(gondolaSeq[key]-1)-key+n)%n+1);
vector<pair<int,int> > targetSeq;
for(int i=0;i<n;i++)
if(gondolaSeq[i]>n) targetSeq.push_back(make_pair(gondolaSeq[i],i));
sort(targetSeq.begin(),targetSeq.end());
int tp=0; //top, return value
for(int i=0;i<targetSeq.size();i++)
{
int ind=targetSeq[i].second;
int val=targetSeq[i].first;
while(tp+n<val)
{
replacementSeq[tp++]=newSeq[ind];
newSeq[ind]=tp+n;
}
}
return tp;
}
//----------------------
static const int mod=1000000009;
static int getpow(int a,int b)
{
if(b==0) return 1;
long long res=getpow(a,b/2);
res=(1LL*res*res)%mod;
if(b%2==1) res=(1LL*res*a)%mod;
return res;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq)) return 0;
vector<int> p;
for(int i=0;i<n;i++)
if(inputSeq[i]>n)
p.push_back(inputSeq[i]);
sort(p.begin(),p.end());
int ginputed=n; //max gondola input
long long ans=1LL;
if(p.size()==n) ans=n;
for(int i=0;i<p.size();i++)
{
ans=(1LL*ans*getpow(p.size()-i,p[i]-ginputed-1))%mod;
ginputed=p[i];
}
return ans;
}
