#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
int i;
int chk[250010];
memset(chk, 0, sizeof(chk));
for (i=0; i<n; i++) chk[inputSeq[i]]++;
for (i=0; i<n; i++) if (chk[inputSeq[i]]!=1) return 0;
for (i=0; i<n; i++) if (inputSeq[i]<=n) break;
if (i>=n) return 1;
int ar[100010];
for (int j=0; j<n; j++) ar[(inputSeq[i]-1+j)%n]=inputSeq[(i+j)%n];
for (i=0; i<n; i++) if (ar[i]<=n&&i+1!=ar[i]) return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int chk[250010]; int i, j;
int ar[100010];
memset(chk, 0, sizeof(chk));
int mx=0;
for (i=0; i<n; i++) mx=max(mx, gondolaSeq[i]);
for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
if (i<n) {
for (j=0; j<n; j++) ar[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
for (i=0; i<n; i++) gondolaSeq[i]=ar[i];
}
for (i=0; i<n; i++) chk[gondolaSeq[i]]=i+1;
int fr=0;
for (i=0; i<n; i++) ar[i]=i+1;
for (i=n+1; i<=mx; i++) {
if (chk[i]) {
replacementSeq[i-n-1]=ar[chk[i]-1];
ar[chk[i]-1]=i;
}
else {
for (; ar[fr]==gondolaSeq[fr]; fr++) {}
replacementSeq[i-n-1]=ar[fr];
ar[fr]=i;
}
}
return mx-n;
}
//----------------------
typedef long long ll;
const ll MAX=1000000009ll;
ll mypow(ll n, int k)
{
if (n==0) return 1;
if (k==0) return 1;
int i;
ll ret=1;
for (i=0; (1<<i)<=k; i++) {} i--;
for (; i>=0; i--) {
ret=ret*ret%MAX;
if ((1<<i)&k) ret=ret*n%MAX;
}
return ret;
}
int arr[100010];
int countReplacement(int n, int gondolaSeq[])
{
if (n==0) return 1;
int i, j;
for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
if (i<n) {
for (j=0; j<n; j++) arr[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
for (i=0; i<n; i++) if (arr[i]<=n&&i+1!=arr[i]) return 0;
}
sort(gondolaSeq, gondolaSeq+n);
for (i=0; i<n-1; i++) if (gondolaSeq[i]==gondolaSeq[i+1]) return 0;
long long ret=1, cnt=0;
for (i=0; i<n; i++) if (gondolaSeq[i]>n) break;
cnt=n-i;
ret=mypow(cnt, gondolaSeq[i]-n-1);
i++;
for (; i<n; i++) {
cnt--;
if (cnt==0) assert(false);
ret=ret*mypow(cnt, gondolaSeq[i]-gondolaSeq[i-1]-1)%MAX;
}
if (gondolaSeq[0]>n) return ret*n%MAX;
return (int)ret;
}
