#include "gondola.h"
#include <bits/stdc++.h>
int valid(int n, int inputSeq[]) {
for (int i = 0; i < n; ++i) {
--inputSeq[i];
}
{
// double
std::set<int> s;
for (int i = 0; i < n; ++i) {
s.insert(inputSeq[i]);
}
if (s.size() != n) {
return false;
}
}
for (int f = 0; f < n; ++f) {
if (inputSeq[f] >= n) {
continue;
}
int x = inputSeq[f];
bool answer = true;
for (int i = f + 1; i < n; ++i) {
const int y = (x + 1) % n;
if (inputSeq[i] < n and y != inputSeq[i]) {
answer = false;
}
x = y;
}
return answer;
}
return true;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
assert(valid(n, gondolaSeq) == 1);
int maxGondola = 0;
for (int i = 0; i < n; ++i) {
maxGondola = std::max(maxGondola, gondolaSeq[i]);
}
std::vector<int> gondolaPos(maxGondola + 1, -1);
for (int i = 0; i < n; ++i) {
gondolaPos[gondolaSeq[i]] = i;
}
std::vector<std::pair<int, int>> eventList;
for (int i = 0; i < n; ++i) {
eventList.push_back({gondolaSeq[i], i});
}
std::sort(eventList.begin(), eventList.end());
std::vector<int> answer;
int spareGondola = n;
std::vector<int> nowGondolaSeq(n, -1);
for (int i = 0; i < n; ++i) {
if (gondolaSeq[i] < n) {
nowGondolaSeq[i] = gondolaSeq[i];
int j = (i + 1) % n, lastVal = nowGondolaSeq[i];
while (j != i) {
lastVal = (lastVal + 1) % n;
nowGondolaSeq[j] = lastVal;
j = (j + 1) % n;
}
break;
}
}
if (nowGondolaSeq[0] == -1) {
std::iota(nowGondolaSeq.begin(), nowGondolaSeq.end(), 0);
}
for (int i = 0; i < n; ++i) {
const auto [v, pos] = eventList[i];
if (v < n) {
continue;
}
int &g = nowGondolaSeq[pos];
while (spareGondola <= v) {
answer.push_back(g);
g = spareGondola++;
}
}
// cvr
for (int i = 0; i < (int)answer.size(); ++i) {
replacementSeq[i] = answer[i] + 1;
}
return (int)answer.size();
}
//----------------------
using i64 = long long;
constexpr i64 mod = 1000000009;
i64 add(i64 a, i64 b) {
return (a + b) % mod;
}
i64 sub(i64 a, i64 b) {
return (a + mod - b) % mod;
}
i64 mul(i64 a, i64 b) {
return (a * b) % mod;
}
void eadd(i64 &a, i64 b) {
a = add(a, b);
}
void esub(i64 &a, i64 b) {
a = sub(a, b);
}
void emul(i64 &a, i64 b) {
a = mul(a, b);
}
i64 moduloPow(i64 a, i64 n) {
i64 ret = 1;
while (n != 0) {
if (n % 2 == 1) {
emul(ret, a);
}
emul(a, a);
n /= 2;
}
return ret;
}
int countReplacement(int n, int inputSeq[]) {
if (valid(n, inputSeq) == 0) {
return 0;
}
std::vector<int> initSeq(n, -1);
for (int i = 0; i < n; ++i) {
if (inputSeq[i] < n) {
initSeq[i] = inputSeq[i];
int j = (i + 1) % n, lastVal = initSeq[i];
while (j != i) {
lastVal = (lastVal + 1) % n;
initSeq[j] = lastVal;
j = (j + 1) % n;
}
break;
}
}
bool isFree = false;
if (initSeq[0] == -1) {
std::iota(initSeq.begin(), initSeq.end(), 0);
isFree = true;
}
std::vector<std::pair<int, int>> eventList;
for (int i = 0; i < n; ++i) {
eventList.push_back({inputSeq[i], i});
}
std::sort(eventList.begin(), eventList.end());
int lastVal = n - 1;
i64 answer = 1;
for (int i = 0; i < n; ++i) {
const auto [v, pos] = eventList[i];
if (v < n) {
continue;
}
const int a = n - i, b = v - lastVal- 1;
const auto k = moduloPow(a, b);
emul(answer, k);
lastVal = v;
}
assert(0 <= answer and answer < mod);
return (int)answer;
}
