#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e6 + 10;
typedef long long ll;
typedef pair<ll, ll> pll;
int A[MAXN];
//----------------------
int replacement(int n, int inputSeq[], int res[]) {
for (int i = 0; i < n; i++) inputSeq[i]--;
int s = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < n)
s = i;
}
int shift_val = (s == -1 ? 0 : (s - inputSeq[s] + n) % n);
for (int j = 0; j < n; j++)
A[j] = inputSeq[(j + shift_val) % n];
set<int> st;
int mx = *max_element(A, A + n);
for (int i = 0; i <= mx; i++)
st.insert(i);
for (int i = 0; i < n; i++)
st.erase(A[i]);
set<pll> gond;
for (int i = 0; i < n; i++)
gond.insert({A[i], i});
int m = 0;
while (gond.rbegin() -> X >= n) {
auto [x, ind] = *prev(gond.end());
gond.erase(prev(gond.end()));
if (st.find(x - 1) != st.end()) {
A[ind] = x - 1;
st.erase(x - 1);
res[m++] = x - 1;
} else {
A[ind] = ind;
st.erase(ind);
res[m++] = ind;
}
gond.insert({A[ind], ind});
}
reverse(res, res + m);
for (int i = 0; i < m; i++)
res[i]++;
return m;
}
//----------------------
const ll MOD = 1e9 + 9;
inline ll poww(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * a % MOD;
b >>= 1;
a = a * a % MOD;
}
return ans;
}
int valid(int n, int inputSeq[]) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
set<int> st;
for (int i = 0; i < n; i++) {
if (st.count(inputSeq[i])) return 0;
st.insert(inputSeq[i]);
}
int lowest = 1e9, pos = 1e9;
for (int i = 0; i < n; i++) {
if (lowest > inputSeq[i]) {
lowest = inputSeq[i], pos = i;
}
}
if (lowest > n) return 1;
for (int i = pos, cnt = lowest, len = 1; len <= n; i = (i + 1) % n, len++, cnt = cnt % n + 1) {
if (inputSeq[i] > n) continue;
if (cnt != inputSeq[i]) return 0;
}
return 1;
}
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq)) return 0;
ll ans = n;
vector<ll> vec;
for (int i = 0; i < n; i++) {
if (inputSeq[i] > n) vec.push_back(inputSeq[i]);
else ans = 1;
}
sort(all(vec));
ll x = n + 1;
for (int i = 0; i < int(vec.size()); i++) {
ans = ans * poww(int(vec.size()) - i, vec[i] - x) % MOD;
x = vec[i] + 1;
}
return ans;
}
