#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
map<int, int> occ;
int valid(int n, int inputSeq[]){
for(int i=0; i<n; i++){
inputSeq[i]--;
if(occ[inputSeq[i]]) return 0;
occ[inputSeq[i]] = 1;
}
int must = -1;
for(int i=0; i<n; i++) if(inputSeq[i] < n) must = i;
if(must == -1) return 1;
for(int i=0; i<n; i++) if(inputSeq[i] < n && (inputSeq[i]+n+must-i)%n != inputSeq[must]) return 0;
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int inputSeq[100005];
for(int i=0; i<n; i++) gondolaSeq[i]--;
int must = -1;
for(int i=0; i<n; i++) if(gondolaSeq[i] < n) must = i;
if(must == -1){
for(int i=0; i<n; i++) inputSeq[i] = i;;
} else{
int cur = gondolaSeq[must];
for(int i=must-1; i>=0; i--){
cur--;
if(cur < 0) cur += n;
inputSeq[i] = cur;
}
cur = gondolaSeq[must];
for(int i=must+1; i<n; i++){
cur++;
if(cur >= n) cur -= n;
inputSeq[i] = cur;
}
}
priority_queue<pair<int, int>> pq;
for(int i=0; i<n; i++) if(gondolaSeq[i] >= n) pq.push({-gondolaSeq[i], i});
int ptr = n-1;
int sz = 0;
while(!pq.empty()){
int num = -pq.top().first;
int pos = pq.top().second;
pq.pop();
while(ptr < num){
replacementSeq[sz++] = inputSeq[pos]+1;
inputSeq[pos] = ++ptr;
}
}
return sz;
}
//----------------------
const int MOD = (1e9)+9;
long long poww(int base, int to){
long long res = 1;
long long cur = base;
while(to){
if(to&1) res *= cur, res %= MOD;
cur *= cur;
cur %= MOD;
to >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq)) return 0;
long long res = 1;
priority_queue<int> pq;
int cnt = 0;
for(int i=0; i<n; i++) if(inputSeq[i] >= n){ pq.push(-inputSeq[i]); cnt++; }
int ptr = n-1;
if(cnt == n) res = n;
while(!pq.empty()){
int num = -pq.top();
pq.pop();
res *= poww(cnt, num-ptr-1);
res %= MOD;
cnt--;
ptr = num;
}
return res;
}
