#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int MOD = 1e9 + 9;
int valid(int n, int inputSeq[]) {
int a[n];
for (int i = 0; i < n; i++) {
a[i] = inputSeq[i];
}
set<int> s;
for (int i = 0; i < n; i++) {
s.insert(a[i]);
}
if ((int) s.size() != n) {
return 0;
}
for (int i = 0; i < n; i++) {
--a[i];
}
int pos = -1;
for (int i = 0; i < n; i++) {
if (a[i] < n) {
pos = i;
}
}
if (pos == -1) {
return 1;
}
int value = a[pos];
for (int i = pos; i < pos + n; i++) {
int idx = i % n;
if (a[idx] < n && a[idx] != value) {
return 0;
}
value = (value + 1) % n;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int a[n];
for (int i = 0; i < n; i++) {
a[i] = gondolaSeq[i];
--a[i];
}
int pos = -1;
for (int i = 0; i < n; i++) {
if (a[i] < n) {
pos = i;
}
}
vector<pair<int, int>> v;
if (pos == -1) {
for (int i = 0; i < n; i++) {
v.emplace_back(a[i], i);
}
} else {
int cur = a[pos];
for (int i = pos; i < pos + n; i++) {
int idx = i % n;
if (a[idx] >= n) {
v.emplace_back(a[idx], cur);
}
cur = (cur + 1) % n;
}
}
sort(begin(v), end(v));
int len = 0;
int cur = n;
int position = 0;
for (auto& [x, y] : v) {
while (cur <= x) {
replacementSeq[position] = y + 1;
++position;
++len;
++cur;
}
}
return len;
}
//----------------------
int countReplacement(int n, int inputSeq[]) {
if (valid(n, inputSeq) == 0) {
return 0;
}
int count = n;
vector<int> v;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
--count;
} else {
v.push_back(inputSeq[i]);
}
}
auto modpow = [&](int a, int b) {
int result = 1;
while (b) {
if (b & 1) {
result = (1ll * result * a) % MOD;
}
a = (1ll * a * a) % MOD;
b >>= 1;
}
return result;
};
sort(v.begin(), v.end());
int cur = n + 1;
int res;
if (count == n) {
res = n; // all the shifts
} else {
res = 1;
}
for (const int& p : v) {
int d = p - cur;
res = (1ll * res * modpow(count, d)) % MOD;
res %= MOD;
res += MOD;
res %= MOD;
cur = p + 1;
--count;
}
return res;
}
// int main() {
// // 1 2
// // 4 3
// int a[] = {1, 2, 7, 6, 10};
// // 0 1 6 5
// // 0 1 2 1
// int b[20];
// int sz = replacement(5, a, b);
// for (int i = 0; i < sz; i++) {
// cout << b[i] << ' ';
// }
// cout << '\n';
// }
