#include "gondola.h"
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
const int MAXN=250010, MOD=1000000009;
int arr[MAXN], pos[MAXN], cp[100010];
int valid(int n, int inputSeq[])
{
forn(i, n) cp[i]=inputSeq[i];
sort(cp, cp+n);
forn(i, n-1) if(cp[i]==cp[i+1]) return 0;
auto itr=min_element(inputSeq, inputSeq+n);
if(*itr>=n) return 1;
auto tmp=itr, last=itr;
while(true){
if(*tmp<=n){
int d1=*tmp-*last, d2=tmp-last;
if(d2<0) d2+=n;
if(d1!=d2) return 0;
last=tmp;
}
tmp++;
if(tmp==inputSeq+n) tmp=inputSeq;
if(tmp==itr) break;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int offset=0;
forn(i, n) if(gondolaSeq[i]<=n) offset=i-gondolaSeq[i]+1;
if(offset<0) offset+=n;
int cur=offset, num=1;
while(true){
arr[cur++]=num++;
if(cur>=n) cur-=n;
if(cur==offset) break;
}
int mx=max_element(gondolaSeq, gondolaSeq+n)-gondolaSeq;
forn(i, gondolaSeq[mx] + 1) pos[i]=-1;
forn(i, n) pos[gondolaSeq[i]]=i;
int ans=0;
forsn(i, n+1, gondolaSeq[mx] + 1){
int p=pos[i];
if(p==-1) p=mx;
replacementSeq[ans++]=arr[p];
arr[p]=i;
}
return ans;
}
//----------------------
ll ex(ll b, ll e){
ll ret=1;
while(e>0){
if(e&1) ret = (ret*b)%MOD;
b = (b*b)%MOD;
e>>=1;
}
return ret;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n, inputSeq)) return 0;
ll ans=1;
int pr=n;
forn(i, n) if(cp[i]>n) ans=(ans*ex(n-i, cp[i]-pr-1))%MOD;
if(cp[0]>n) ans=(ans*n)%MOD;
return ans;
}
