#include "gondola.h"
#include <bits/stdc++.h>
#define ii pair<int, int>
using namespace std;
bitset<250001> mark;
int valid(int n, int inputSeq[])
{
int idx = 0;
for(int i = 0; i < n; i++){
if(mark[inputSeq[i]]) return 0;
mark[inputSeq[i]] = 1;
if(idx == 0 && inputSeq[i] <= n){
idx = inputSeq[i];
}
if(idx != 0 && inputSeq[i] <= n && inputSeq[i] != idx) return 0;
if(idx != 0) idx++;
if(idx > n) idx = 1;
}
return 1;
}
//----------------------
int a[100001];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int idx = 0;
priority_queue<ii, vector<ii>, greater<ii> > pq;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] > n){
pq.push({gondolaSeq[i], i});
}
if(idx == 0 && gondolaSeq[i] <= n){
idx = gondolaSeq[i];
for(int j = i - 1, tmp = idx - 1; j >= 0; j--, tmp--){
if(tmp <= 0) tmp += n;
a[j] = tmp;
}
}
if(idx != 0){
a[i] = idx;
idx++;
}
if(idx > n) idx = 1;
}
if(idx == 0){
for(int i = 0; i < n; i++) a[i] = i + 1;
}
int replace_idx = n + 1, ans_idx = 0;
while(!pq.empty()){
int k = pq.top().first;
int id = pq.top().second;
pq.pop();
while(replace_idx <= k){
replacementSeq[ans_idx++] = a[id];
a[id] = replace_idx;
replace_idx++;
}
}
return ans_idx;
}
//----------------------
const long long md = 1e9 + 9;
long long pw(long long a, long long b){
if(b == 0) return 1ll;
if(b == 1) return a;
long long e = pw(a, b >> 1);
if(b % 2) return ((e * e) % md) * a % md;
return (e * e) % md;
}
int countReplacement(int n, int inputSeq[])
{
if(valid(n, inputSeq) == 0) return 0;
long long ans = 1, chk = 0;
priority_queue<int, vector<int>, greater<int> > pq;
for(int i = 0; i < n; i++){
if(inputSeq[i] > n) pq.push(inputSeq[i]);
else chk = 1;
}
if(!chk) ans = n * 1ll;
if(pq.empty()) return 1;
pq.push(n);
while(pq.size() > 1){
int u = pq.top(); pq.pop();
int v = pq.top();
ans = (ans * pw(pq.size() * 1ll, (v - u - 1) * 1ll)) % md;
}
return int(ans);
}
