#include <bits/stdc++.h>
#include <gondola.h>
int valid(int n, int inputSeq[])
{
std::map<int,bool> existe;
for(int i = 0;i!=n;++i){
auto&x=inputSeq[i];
if(existe[x]){
return false;
}
existe[x]=true;
}
int ind = -1;
int val=1e6;
for(int i=0;i!=n;++i){
if(inputSeq[i]<=n){
if(inputSeq[i]<val){
val=inputSeq[i];
ind=i;
}
}
}
if(ind==-1)ind=0;
if(val>n){return true;}
int imaginario[n];
int count = inputSeq[ind];
if(ind==-1)count=0;
for(int i=ind;i!=n;++i){
imaginario[i]=count;
++count;
}
for(int i=0;i!=ind;++i){
imaginario[i]=count;
++count;
}
for(int i=0;i!=n;++i) {
if(inputSeq[i]>n)continue;
if(inputSeq[i]!=imaginario[i]){return false;}
}
return true;
}
//----------------------
long long modpow(long long a,long long b){
if(!b)return 1;
const long long mod = 1e9+9;
typedef std::pair<long long,long long> pll;
std::vector<pll> vec;
long long c = 1;
long long val = a;
vec.push_back({1,val});
while(c<b){
c*=2;
val=(val*val)%mod;
vec.push_back({c,val});
}
long long resp = 1;
while(vec.size()){
while(vec.back().first<=b){
b-=vec.back().first;
resp=(resp*vec.back().second)%mod;
}
vec.pop_back();
}
return resp;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int array[n];
for(int i=0;i!=n;++i)
array[i]=gondolaSeq[i];
std::map<int,int> vec;
int max=0;
for(int i=0;i!=n;++i){
if(array[i]>n){
vec[array[i]]=i;
max=std::max(max,array[i]);
}
}
if(!max)return 0;
int cursor=0;
int ind = -1;
int val=1e6;
for(int i=0;i!=n;++i){
if(array[i]<=n){
if(array[i]<val){
val=array[i];
ind=i;
}
}
}
int imaginario[n];
int count = array[ind];
if(ind==-1){count=1;ind=0;}
for(int i=ind;i!=n;++i){
imaginario[i]=count%(n);
if(!imaginario[i])imaginario[i]=n;
++count;
}
for(int i=0;i!=ind;++i){
imaginario[i]=count%(n);
if(!imaginario[i])imaginario[i]=n;
++count;
}
for(;;){
int proxima_gondola = cursor+n+1;
auto it = vec.find(proxima_gondola);
if(it==vec.end()){
int subs = vec.begin()->second;
replacementSeq[cursor]=imaginario[subs];
imaginario[subs]=proxima_gondola;
}else {
int subs = it->second;
replacementSeq[cursor]=imaginario[subs];
imaginario[subs]=proxima_gondola;
vec.erase(it);
}
++cursor;
if(!vec.size())break;
}
return cursor;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
if(!valid(n,inputSeq))return 0;
int array[n];
for(int i=0;i!=n;++i)
array[i]=inputSeq[i];
std::priority_queue<int,std::vector<int>,std::greater<int>> queue;
int count=0;
for(int i=0;i!=n;++i){
if(array[i]>n){
queue.push(array[i]);
count++;
}
}
int gondola = n+1;
long long resp = 1;
if(count==n)resp=n;
const long long mod = 1e9+9;
while(count){
int proximo = queue.top();
int movs = proximo-gondola;
long long x = modpow(count,movs);
gondola=queue.top()+1;
queue.pop();
resp=(resp*x)%mod;
--count;
}
return resp;
}
