#include "gondola.h"
#include <iostream>
#include <set>
#include <algorithm>
#define MOD 1000000009
int arr[250001];
int now[250001];
using namespace std;
int valid(int n, int inputSeq[]) {
int start = 0;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
start = i;
break;
}
}
if (start < n) {
for (int j = 0; j < n; j++) {
if (inputSeq[j] <= n && (inputSeq[j] + start) % n != (inputSeq[start] + j) % n) return 0;
}
}
sort(inputSeq, inputSeq + n);
for (int i = 1; i < n; i++) {
if (inputSeq[i - 1] == inputSeq[i]) {
return 0;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int i,j;
for(i=0;i<n;i++)arr[gondolaSeq[i]]=i+1;
for(i=0;i<n;i++)if(gondolaSeq[i]<=n)break;
for(j=0;j<n;j++)now[j]=i<n?(gondolaSeq[i]+j-i+n-1)%n+1:j+1;
j=0;
for(i=0;i<n;i++)if(gondolaSeq[i]>j)j=gondolaSeq[i];
for(i=n+1;i<=j;i++)
{
replacementSeq[i-n-1]=arr[i]>0?now[arr[i]-1]:now[arr[j]-1];
now[arr[i]>0?arr[i]-1:arr[j]-1]=i;
}
return j-n;
}
int f(int x,int y)
{
if(y==0||x==1)return 1;
if(y&1)return 1LL*x*f(x,y-1)%MOD;
x=f(x,y>>1);
return 1LL*x*x%MOD;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))return 0;
int i,r=1;
std::sort(inputSeq,inputSeq+n);
for(i=0;i<n;i++)
{
if(inputSeq[i]<=n)continue;
r=1LL*r*f(n-i,inputSeq[i]-(i>0?std::max(inputSeq[i-1],n):n)-1)%MOD;
}
return 1LL*r*(inputSeq[0]>n?n:1)%MOD;
}
