#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
int valid(int n, int inputSeq[])
{
int shift=-1;
int i;
for(i=0;i<n;++i)
if(inputSeq[i]<=n){
if(shift==-1)
shift=(i+1-inputSeq[i]+n)%n;
else
if((i+1-shift+n)%n!=inputSeq[i]%n)
return 0;
}
sort(inputSeq,inputSeq+n);
for(i=0;i<n-1;++i)
if(inputSeq[i]==inputSeq[i+1])
return 0;
return 1;
}
struct per{
int val,pos;
bool operator<(per ot){
return val>ot.val;
}
};
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int shift=-1;
int i;
for(i=0;i<n;++i)
if(gondolaSeq[i]<=n)
shift=(i+1-gondolaSeq[i]+n)%n;
if(shift==-1)
shift=0;
vector<per>v;
for(i=0;i<n;++i)
if(gondolaSeq[i]>n)
v.push_back({gondolaSeq[i],i});
int len=0;
if(!v.empty()){
sort(v.begin(),v.end());
int ult=(v[0].pos-shift+n)%n+1;
while(!v.empty()){
++len;
if(n+len==v.back().val){
replacementSeq[len-1]=((v.size()>1)?((v.back().pos-shift+n)%n+1):ult);
v.pop_back();
}
else{
replacementSeq[len-1]=ult;
ult=n+len;
}
}
}
return len;
}
int const MOD=1e9+9;
int bin_exp(int base,int exp){
int rez=1;
while(exp){
if(exp&1)
rez=1LL*rez*base%MOD;
base=1LL*base*base%MOD;
exp/=2;
}
return rez;
}
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))
return 0;
int rez=1;
vector<int>v;
int i;
for(i=0;i<n;++i)
if(inputSeq[i]>n)
v.push_back(inputSeq[i]);
sort(v.rbegin(),v.rend());
if(v.size()==n)
rez=n;
int ult=n;
while(!v.empty()){
rez=1LL*rez*bin_exp(v.size(),v.back()-ult-1)%MOD;
ult=v.back();
v.pop_back();
}
return rez;
}
