#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;
for(int i = 0;i<n;++i){
if(s.find(inputSeq[i]) != s.end()){
return 0;
}
s.insert(inputSeq[i]);
}
int pos = -1;
for(int i = 0;i<n;++i){
if(inputSeq[i] <= n){
if(pos == -1){
pos = i;
}
else{
int ch = i+inputSeq[pos]-pos+n;
ch %= n;
if(ch == 0) ch = n;
if(inputSeq[i] != ch) 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;
shift %= n;
}
}
priority_queue<pair<int,int>> pq;
for(int i = 0;i<n;++i){
int realpos = (i-shift+n)%n;
if(gondolaSeq[realpos] > n){
pq.push({gondolaSeq[realpos],i+1});
}
}
int l = 0, cur = n+1; //length of the replacement sequence
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 pow(int a, int x){
ll res = 1, cur = a;
while(x != 0){
if(x & 1) res *= cur;
cur *= cur;
cur %= MOD;
res %= MOD;
x /= 2;
}
return res;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n,inputSeq)) return 0;
int num = 0;
int newseq[100005] = {};
for(int i = 0;i<n;++i){
if(inputSeq[i] > n){
newseq[num++] = inputSeq[i];
}
}
if(num == 0) return 1;
sort(newseq,newseq+num);
long long ans = 1; int cnt = num;
if(num == n) ans = num;
int last = n;
for(int i = 0;i<num;++i){
ans *= pow(cnt,newseq[i]-last-1);
ans %= MOD;
last = newseq[i];
cnt--;
}
return (int)ans;
}
