#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int X = 1e6 + 1, N = 250001, MOD = 1e9 + 9;
int inv[X], tmp[N];
int valid(int n, int inputSeq[]) {
memset(inv, -1, sizeof(inv));
for (int i = 0; i < n; ++i) {
if (inputSeq[i] <= n) {
inv[inputSeq[i]] = i;
}
}
memcpy(tmp, inputSeq, sizeof(tmp[0]) * n);
sort(tmp, tmp + n);
if (unique(tmp, tmp + n) != tmp + n) {
return 0;
}
int offset = -1;
for (int x = 1; x <= n; ++x) {
if (inv[x] != -1) {
int now = x - inv[x];
if (now < 0) now += n;
if (offset != -1 && offset != now) {
return 0;
}
offset = now;
}
}
return 1;
}
int replacement(int n, int inputSeq[], int replacementSeq[]) {
memset(inv, -1, sizeof(inv));
const int A = *max_element(inputSeq, inputSeq + n);
if (A == n) {
return 0;
}
for (int i = 0; i < n; ++i) {
if (inv[inputSeq[i]] != -1) {
return 0;
}
inv[inputSeq[i]] = i;
}
int offset = -1;
for (int x = 1; x <= n; ++x) {
if (inv[x] != -1) {
int now = x - inv[x];
if (now < 0) now += n;
if (offset != -1 && offset != now) {
return 0;
}
offset = now;
}
}
vector<int> initial(n);
if (offset == -1) {
iota(initial.begin(), initial.end(), 1);
} else {
for (int x = 1; x <= n; ++x) {
int i = x - offset;
if (i < 0) i += n;
initial[i] = x;
}
}
set<int> st;
for (int i = 0; i < n; ++i) {
if (inputSeq[i] != initial[i]) {
st.insert(i);
}
}
int l = 0;
for (int x = n + 1; x <= A; ++x) {
int i;
if (inv[x] != -1) {
i = inv[x];
} else {
i = *st.begin();
}
replacementSeq[l++] = initial[i];
initial[i] = x;
if (initial[i] == inputSeq[i]) {
st.erase(i);
}
}
return l;
}
int power(int a, int b) {
int res = 1;
for (; b > 0; b >>= 1, a = 1LL * a * a % MOD) {
if (b & 1) {
res = 1LL * a * res % MOD;
}
}
return res;
}
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq)) {
return 0;
}
memset(inv, -1, sizeof(inv));
const int A = *max_element(inputSeq, inputSeq + n);
for (int i = 0; i < n; ++i) {
if (inputSeq[i] <= n) {
inv[inputSeq[i]] = i;
}
}
int offset = -1;
for (int x = 1; x <= n; ++x) {
if (inv[x] != -1) {
int now = x - inv[x];
if (now < 0) now += n;
if (offset != -1 && offset != now) {
return 0;
}
offset = now;
}
}
vector<int> initial(n);
constexpr int MOD = 1e9 + 9;
int ans = 1;
if (offset == -1) {
iota(initial.begin(), initial.end(), 1);
ans = n;
} else {
for (int x = 1; x <= n; ++x) {
int i = x - offset;
if (i < 0) i += n;
initial[i] = x;
}
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (inputSeq[i] != initial[i]) {
cnt += 1;
}
}
sort(inputSeq, inputSeq + n);
int last = n;
for (int ii = 0; ii < n; ++ii) {
int x = inputSeq[ii];
if (x <= n) {
continue;
}
ans = 1LL * ans * power(cnt, x - last - 1) % MOD;
last = x;
cnt -= 1;
}
return ans;
}
