#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 250005, mod = 1000000009;
int poz[maxN];
int lgput(int x, int p) {
if (p == 0) {
return 1;
}
int k = lgput(x, p/2);
int ans = 1LL * k * k % mod;
if (p % 2 == 1) {
ans = 1LL * ans * x % mod;
}
return ans;
}
int valid(int n, int inputSeq[]) {
for (int i = 1; i <= n; i++) {
int x = inputSeq[i - 1];
if (poz[x]) {
return 0;
}
poz[x] = i;
}
int last = 1, pLast = poz[1];
for (int i = 2; i <= n; i++) {
if (poz[i] == 0) {
continue;
}
if (pLast == 0) {
last = i;
pLast = poz[i];
continue;
}
int diff = poz[i] - pLast;
if (diff < 0) {
diff += n;
}
if (diff != i - last) {
// cout << last << ' ' << pLast << ' ' << i << ' ' << poz[i] << '\n';
return 0;
}
last = i;
pLast = poz[i];
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
vector <int> extras;
int root = 1, pRoot = 1;
for (int i = 1; i <= n; i++) {
int x = gondolaSeq[i - 1];
if (x > n) {
extras.push_back(x);
} else {
root = x;
pRoot = i;
}
poz[x] = i;
}
sort(extras.begin(), extras.end());
int p = 0, last = n + 1;
for (int i = 0; i < extras.size(); i++) {
int x = extras[i];
int trueNumber = (root + (poz[x] - pRoot + n) % n) % n;
if (trueNumber == 0) {
trueNumber += n;
}
replacementSeq[p++] = trueNumber;
while (last < extras[i]) {
replacementSeq[p++] = last;
last++;
}
last++;
}
return p;
}
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq)) {
cout << "here?\n";
return 0;
}
int total = 0;
vector <int> extras;
for (int i = 1; i <= n; i++) {
int x = inputSeq[i - 1];
if (x > n) {
extras.push_back(x);
}
poz[x] = i;
total = max(total, x);
}
total -= n;
if (total == 0) {
return 1;
}
sort(extras.begin(), extras.end());
reverse(extras.begin(), extras.end());
extras.push_back(n);
int ans = 1;
for (int i = 1; i < extras.size(); i++) {
int diff = extras[i - 1] - extras[i] - 1;
ans = 1LL * ans * lgput(i, diff) % mod;
}
return ans;
}
