#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]) {
for (int i = 0; i < n; i++) {
inputSeq[i]--;
}
int beg = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < n) {
beg = (inputSeq[i] - i + n) % n;
}
}
if (beg != -1) {
for (int i = 0; i < n; i++) {
if (inputSeq[i] < n) {
if (inputSeq[i] != (beg + i) % n) {
return 0;
}
}
}
}
sort(inputSeq, inputSeq + n);
if (unique(inputSeq, inputSeq + n) - inputSeq != n) {
return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
for (int i = 0; i < n; i++) {
gondolaSeq[i]--;
}
int beg = -1;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] < n) {
beg = (gondolaSeq[i] - i + n) % n;
}
}
vector<pair<int, int>> rpl;
for (int i = 0; i < n; i++) {
if (beg == -1) {
rpl.push_back(make_pair(gondolaSeq[i], i));
} else if (gondolaSeq[i] != (beg + i) % n) {
rpl.push_back(make_pair(gondolaSeq[i], (beg + i) % n));
}
}
sort(rpl.begin(), rpl.end());
int mx = 0;
set<int> opg;
for (int i = 0; i < n; i++) {
mx = max(mx, gondolaSeq[i]);
opg.insert(gondolaSeq[i]);
}
vector<int> ext;
for (int i = n; i <= mx; i++) {
if (!opg.count(i)) {
ext.push_back(i);
}
}
int ret = 0, j = 0;
for (int i = 0; i < (int)rpl.size(); i++) {
replacementSeq[ret++] = rpl[i].second + 1;
while (j < (int)ext.size() && ext[j] < rpl[i].first) {
replacementSeq[ret++] = ext[j] + 1;
j++;
}
}
return ret;
}
int countReplacement(int n, int inputSeq[]) {
int validSeq[100000] = {};
for (int i = 0; i < n; i++) {
validSeq[i] = inputSeq[i];
}
if (valid(n, validSeq) == 0) {
return 0;
}
for (int i = 0; i < n; i++) {
inputSeq[i]--;
}
int beg = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] < n) {
beg = (inputSeq[i] - i + n) % n;
}
}
vector<int> rpl;
for (int i = 0; i < n; i++) {
if (beg == -1 || inputSeq[i] != (beg + i) % n) {
rpl.push_back(inputSeq[i]);
}
}
rpl.push_back(n - 1);
sort(rpl.begin(), rpl.end());
#define MOD 1000000009
auto fpow = [](int a, int b) {
int ret = 1;
while (b) {
if (b & 1) {
ret = (long long)ret * a % MOD;
}
a = (long long)a * a % MOD;
b >>= 1;
}
return ret;
};
int ans = 1;
if (beg == -1) {
ans = n;
}
for (int i = 1; i < (int)rpl.size(); i++) {
ans = ans * fpow(rpl.size() - i, rpl[i] - rpl[i - 1] - 1) % MOD;
}
#undef MOD
return ans;
}
