#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
int valid(int n, int v[]) {
map<int, bool> freq;
int mi = -1;
for (int i = 0; i < n; i++) {
if (freq[v[i]]) return 0;
freq[v[i]] = 1;
if (v[i] <= n && (mi == -1 || v[i] < v[mi])) {
mi = i;
}
}
if (mi == -1) {
return 1;
}
int prevj = mi;
for (int j = mi + 1; j <= (n + mi - 1); j++) {
int i = j % n;
if (v[i] > n) continue;
// cout << prevj << ' ' << j << '\n';
// cout << v[prevj % n] << ' ' << (v[i]) << '\n';
// cout << abs(j - prevj) << ' ' << abs(v[i] - v[prevj % n]) << '\n';
// cout << '\n';
if (v[i] < v[prevj % n] or abs(j - prevj) != abs(v[i] - v[prevj % n])) return 0;
prevj = j;
}
return 1;
}
//----------------------
int replacement(int n, int v[], int ans[]) {
int LASTI = -1;
function<void(int)> pb = [&](int a) {
LASTI++;
ans[LASTI] = a;
};
int mi = -1;
for (int i = 0; i < n; i++) {
if (v[i] <= n && (mi == -1 || v[i] < v[mi])) {
mi = i;
}
}
vector<int> original(n);
if (mi == -1) {
iota(original.begin(), original.end(), 1);
} else {
int set = v[mi];
for (int i = 1; set - i > 0; i++) {
int j = (mi - i);
if (j < 0) j = n + j;
original[j] = set - i;
}
for (int i = 1; set + i <= n; i++) {
int j = (mi + i) % n;
original[j] = set + i;
}
}
original[mi] = v[mi];
vector<pair<int, int>> ord;
for (int i = 0; i < n; i++) {
if (v[i] > n) ord.push_back({v[i], original[i]});
}
sort(ord.begin(), ord.end());
int count = 0;
int last = n + 1;
for (int i = 0; i < ord.size(); i++) {
// cout << last << ' ' << ord[i].first << '\n';
int run = 0;
while (last != ord[i].first + 1) {
if (run == 0) {
pb(ord[i].second);
} else {
pb(last - 1);
}
count++, last++, run++;
}
}
return count;
}
//----------------------
int countReplacement(int n, int v[]) {
ull MOD = 1e9 + 9;
ull ONE = 1;
ull ZERO = 0;
function<ull(int, int)> pow = [&](int a, int n) {
if (a == 0) return ZERO;
if (n == 0) return ONE;
if (n == 1) {
return ONE*a;
}
ull half = ONE*pow(a, n/2) % MOD ;
ull res = (half*half) % MOD;
if (n % 2 == 1) {
return res*ONE*a % MOD;
}
return res;
};
if (!valid(n, v)) {
return 0;
}
vector<int> res;
for (int i = 0; i < n; i++) {
if (v[i] > n) res.push_back(v[i] - n);
}
if (res.size() == 0) {
return 1;
}
sort(res.begin(), res.end());
ull ans = pow((int)res.size(), res[0] - 1) * (res.size() == n ? ONE*n : 1) % MOD;
for (int i = 1; i < res.size(); i++) {
ull r = pow((int)res.size() - i, res[i] - res[i - 1] - 1);
// cout << r << '\n';
ans *= (r%MOD);
ans %= MOD;
}
return (int)ans;
}
