#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD = 1e9+9;
int valid(int n, int inputSeq[]){
set<int> s;
int pos = -1;
for(int i = 0;i<n;++i){
if(s.find(inputSeq[i]) != s.end()) return 0;
if(inputSeq[i] <= n && pos == -1){
pos = i;
}
s.insert(inputSeq[i]);
}
if(pos == -1) return 1;
for(int i = 0;i<n;++i){
if(inputSeq[i] <= n && i != pos){
int d = (inputSeq[pos]+i-pos+n)%n;
if(d == 0) d = n;
if(d != inputSeq[i]) return 0;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int shift = -1;
for(int i = 0;i<n;++i){
if(gondolaSeq[i] <= n){
shift = (gondolaSeq[i]-i-1+n)%n;
}
}
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
for(int i = 0;i<n;++i){
int d = (i-shift+n)%n;
if(gondolaSeq[d] > n){
pq.push({gondolaSeq[d],i+1});
}
}
int l = 0, cur = n+1;
while(!pq.empty()){
pair<int,int> p = pq.top(); pq.pop();
replacementSeq[l++] = p.second;
for(int i = cur;i<p.first;++i) replacementSeq[l++] = i;
cur = p.first+1;
}
return l;
}
ll binpow(int x, int k){
ll ans = 1, p = x;
while(k != 0){
if(k & 1) ans *= p;
p *= p;
p %= MOD;
ans %= MOD;
k /= 2;
}
return ans;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n,inputSeq)) return 0;
int newseq[100005] = {};
int cnt = 0;
for(int i = 0;i<n;++i){
if(inputSeq[i] > n){
newseq[cnt++] = inputSeq[i];
}
}
sort(newseq,newseq+cnt);
int last = n, cur = cnt; ll ans = 1;
if(cnt == n) ans = n;
for(int i = 0;i<cnt;++i){
ans *= binpow(cur,newseq[i]-last-1);
ans %= MOD;
last = newseq[i];
cur--;
}
return (int)ans;
}
