#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const long long MOD = (long long) 1e9 + 9;
int valid(int n, int inputSeq[]) {
int pos = -1;
set<int> used;
for (int i = 0; i < n; i++) {
if (used.count(inputSeq[i])) {
return 0;
}
used.insert(inputSeq[i]);
if (inputSeq[i] <= n) {
pos = i;
}
}
if (pos == -1) {
return 1;
}
int cur = inputSeq[pos] - pos;
if (cur < 1) {
cur = n + cur;
}
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n && inputSeq[i] != cur) {
return 0;
}
cur++;
if (cur > n) {
cur = 1;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int mx = *max_element(gondolaSeq, gondolaSeq + n);
vector<int> pos(mx + 1, -1);
int st = -1, tmp = -1;
for (int i = 0; i < n; i++) {
pos[gondolaSeq[i]] = i;
if (gondolaSeq[i] > n) {
if (st == -1 || gondolaSeq[i] > gondolaSeq[st]) {
st = i;
}
} else {
tmp = i;
}
}
vector<int> a(n);
if (tmp == -1) {
a[0] = 1;
} else {
a[0] = gondolaSeq[tmp] - tmp;
if (a[0] < 1) {
a[0] = n + a[0];
}
}
for (int i = 1; i < n; i++) {
a[i] = a[i - 1] + 1;
if (a[i] > n) {
a[i] = 1;
}
}
int l = 0;
for (int i = n + 1; i <= mx; i++) {
if (pos[i] == -1) {
replacementSeq[l++] = a[st];
a[st] = i;
} else {
replacementSeq[l++] = a[pos[i]];
a[pos[i]] = i;
}
}
return l;
}
//----------------------
template<typename T>
T modpow(T b, T p) {
if (p == 0) {
return 1;
}
T ans = modpow(b * b % MOD, p / 2);
if (p % 2 == 1) {
ans = (ans * b) % MOD;
}
return ans;
}
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq)) {
return 0;
}
int pos = -1, cnt = 0;
vector<int> v;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
pos = i;
} else {
cnt++;
v.push_back(inputSeq[i]);
}
}
sort(v.begin(), v.end());
long long ans = 1;
int prev = n;
for (auto& x : v) {
ans = (ans * modpow((long long) cnt, (long long) (x - prev - 1))) % MOD;
cnt--;
prev = x;
}
if (pos == -1) {
ans = (ans * (long long) n) % MOD;
}
return ans;
}
