#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long ll;
int valid(int n,int inputSeq[])
{
vector<int> v(n);
for(int i=0;i<n;i++) v[i]=inputSeq[i];
for(int i=0;i<n;i++)
{
if(v[i]<=n)
{
int one=(i-(v[i]-1)+n)%n;
rotate(v.begin(),v.begin()+one,v.end());
break;
}
}
set<int> s;
for(int i=0;i<n;i++)
{
if(s.find(v[i])!=s.end()) return 0;
s.insert(v[i]);
if(v[i]<=n&&v[i]!=i+1) return 0;
}
return 1;
}
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
vector<int> v(n);
for(int i=0;i<n;i++) v[i]=gondolaSeq[i];
for(int i=0;i<n;i++)
{
if(v[i]<=n)
{
int one=(i-(v[i]-1)+n)%n;
rotate(v.begin(),v.begin()+one,v.end());
break;
}
}
vector<int> trains[n];
for(int i=0;i<n;i++) trains[i].push_back(i+1);
int mx=0;
for(int i=1;i<n;i++) if(v[i]>v[mx]) mx=i;
vector<int> vis(v[mx]+1,0);
for(int i=0;i<n;i++) vis[v[i]]=1;
for(int i=n+1;i<=v[mx];i++) if(vis[i]==0) trains[mx].push_back(i);
for(int i=0;i<n;i++) trains[i].push_back(v[i]);
vector<int> res(v[mx]+1,0);
for(int i=0;i<n;i++) for(int j=1;j<(int)trains[i].size();j++) res[trains[i][j]]=trains[i][j-1];
for(int i=n+1;i<=v[mx];i++) replacementSeq[i-n-1]=res[i];
return v[mx]-n;
}
int countReplacement(int n,int inputSeq[])
{
if(valid(n,inputSeq)==0) return 0;
const ll mod=1000000009;
auto mul=[&](ll a,ll b)->ll{return (a*b)%mod;};
auto fpow=[&](ll b,ll e)->ll
{
ll r=1;
while(e)
{
if(e&1) r=mul(r,b);
b=mul(b,b);
e/=2;
}
return r;
};
vector<int> v={n};
for(int i=0;i<n;i++) if(inputSeq[i]>=n+1) v.push_back(inputSeq[i]);
sort(v.begin(),v.end());
int sz=v.size();
ll res=1;
for(int i=1;i<sz;i++) res=mul(res,fpow(sz-i,v[i]-v[i-1]-1));
return int(res);
}
