#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 9;
int valid(int n, int a[]){
map<int, bool> exist;
int app = -1;
for (int i = 0; i < n; ++i){
if (exist[a[i]]) return false;
exist[a[i]] = true;
if (a[i] <= n && app == -1) app = i;
}
if (app == -1) return 1;
for (int i = app + 1; i < n; ++i){
if (a[i] <= n){
if (a[i] == 1 && a[i - 1] != n) return 0;
if (a[i] != 1 && a[i - 1] + 1 != a[i]) return 0;
}
else a[i] = a[i - 1] + 1;
}
return 1;
}
int replacement(int n, int a[], int replacementSeq[]){
int opt = 0, cur = n, st = -1;
vector<pair<int, int>> v;
for (int i = 0; i < n; ++i){
if (a[i] <= n && st == -1) st = i;
}
if (st == -1){
st = 0;
v.push_back({1, a[0]});
a[0] = 1;
}
for (int i = st + 1; i < n; ++i){
if (a[i] > n){
v.push_back({a[(i - 1 + n) % n] % n + 1, a[i]});
a[i] = a[(i - 1 + n) % n] % n + 1;
}
}
for (int i = 0; i < st; ++i){
if (a[i] > n){
v.push_back({a[(i - 1 + n) % n] % n + 1, a[i]});
a[i] = a[(i - 1 + n) % n] % n + 1;
}
}
sort(v.begin(), v.end(), [](const pair<int, int>& x, const pair<int, int>& y){
return x.second < y.second;
});
for (int i = 0; i < v.size(); ++i){
int first = v[i].first, second = v[i].second;
while (first < second){
replacementSeq[opt] = first;
opt++;
first = ++cur;
}
}
return opt;
}
long long binpow(long long base, long long e){
long long res = 1;
while (e > 0){
if (e & 1) res = (res * base) % mod;
base = base * base % mod;
e /= 2;
}
return res;
}
int countReplacement(int n, int a[]){
int cur = n, st = -1;
long long res = 1;
vector<int> v;
for (int i = 0; i < n; ++i){
if (a[i] <= n && st == -1) st = i;
}
for (int i = 0; i < n; ++i) if (a[i] > n)
v.push_back(a[i]);
if (valid(n, a) == 0) return 0;
sort(v.begin(), v.end());
int cnt = v.size();
for (int x : v){
res = res * binpow(cnt, x - 1 - cur) % mod;
cur = x;
cnt--;
}
if (st == -1) res = res * n % mod;
return res;
}
