#include "gondola.h"
#include <queue>
#include <set>
#include <utility>
// meeeow mrrowww :3
// go play vivid/stasis! it's a very awesome free game on steam
using namespace std;
int valid(int n, int inputSeq[]) {
int offset_got = false, offset;
set<int> had_bigger;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
if (offset_got) {
if ((inputSeq[i] + offset + n) % n != i) return false;
} else {
offset_got = true;
offset = i - inputSeq[i];
}
} else {
if (had_bigger.count(inputSeq[i])) return false;
had_bigger.insert(inputSeq[i]);
}
}
return true;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int offset;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] <= n) {
offset = i - gondolaSeq[i];
break;
}
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] > n) q.emplace(gondolaSeq[i] - n, (i - offset - 1 + n + n) % n + 1);
}
int l = 0;
while (q.size()) {
auto [m, r] = q.top();
q.pop();
for (int i = 0; i < m; i++) {
replacementSeq[l++] = r;
r = n + l;
}
}
return l;
}
long long pow(long long a, long long b) {
long long res = 1;
while (b) {
if (b & 1) { res = (res * a) % 1000000009; }
a = (a * a) % 1000000009;
b >>= 1;
}
return res;
}
int countReplacement(int n, int inputSeq[]) {
int offset_got = false, offset;
priority_queue<int, vector<int>, greater<int>> q;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
if (offset_got) {
if ((inputSeq[i] + offset + n) % n != i) return 0;
} else {
offset_got = true;
offset = i - inputSeq[i];
}
} else {
q.push(inputSeq[i]);
}
}
long long res = 1;
int p = n;
while (q.size()) {
int v = q.top();
res = (res * pow(q.size(), v - p - 1)) % 1000000009;
p = v;
q.pop();
}
if (!offset_got) res = (res * n) % 1000000009;
return res;
}
