#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 = 1; i < n; ++i){
int idx = (app + i) % n;
int expect = (a[app] + i - 1) % n + 1;
if (a[idx] <= n && a[idx] != expect) return 0;
}
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 st = -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(), cur = n;
long long res = 1;
for (int x : v){
res = res * binpow(1LL * cnt, (long long)(x - 1 - cur)) % mod;
cur = x;
cnt--;
}
if (st == -1) res = 1LL * res * (long long) n % mod;
return res;
}
