#include "gondola.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+9;
int bp(int a, int n) {
if (!n) return 1;
if (n % 2) return a * bp(a, n - 1) % MOD;
int b = bp(a, n / 2);
return b * b % MOD;
}
int32_t valid(int32_t n, int32_t inputSeq[])
{
vector <int> a(n);
int flag = 0;
for (int i = 0; i < n; i ++) {
if (inputSeq[i] <= n) {
a[i] = inputSeq[i];
for (int j = i + 1; j < n; j ++) {
a[j] = (a[j-1] + 1) % n;
if (!a[j]) a[j] = n;
}
if (i) {
a[0] = (a[n-1] + 1) % n;
if (!a[0]) a[0] = n;
}
for (int j = 1; j < i; j ++) {
a[j] = (a[j-1] + 1) % n;
if (!a[j]) a[j] = n;
}
flag = 1;
break;
}
}
vector <int> tmp(n);
for (int i = 0; i < n; i ++) {
tmp[i] = inputSeq[i];
}
sort(tmp.begin(), tmp.end());
for (int i = 1; i < n; i ++) {
if (tmp[i] == tmp[i-1]) return 0;
}
if (!flag) return 1;
for (int i = 0; i < n; i ++) {
if (inputSeq[i] <= n and inputSeq[i] != a[i]) return 0;
}
return 1;
}
//----------------------
int32_t replacement(int32_t n, int32_t gondolaSeq[], int32_t replacementSeq[])
{
vector <int> a(n);
vector <pair <int, int>> p;
int flag = 0;
for (int i = 0; i < n; i ++) {
if (gondolaSeq[i] <= n) {
a[i] = gondolaSeq[i];
for (int j = i + 1; j < n; j ++) {
a[j] = (a[j-1] + 1) % (n + 1);
a[j] = max(1ll, a[j]);
}
if (i) {
a[0] = (a[n-1] + 1) % (n + 1);
a[0] = max(1ll, a[0]);
}
for (int j = 1; j < i; j ++) {
a[j] = (a[j-1] + 1) % (n + 1);
a[j] = max(1ll, a[j]);
}
flag = 1;
break;
}
}
if (!flag) {
for (int i = 0; i < n; i ++) {
a[i] = i + 1;
}
}
for (int i = 0; i < n; i ++) {
if (gondolaSeq[i] > n) p.push_back({gondolaSeq[i], a[i]});
}
sort(p.begin(), p.end());
int last = n + 1, pos = 0;
for (auto i: p) {
replacementSeq[pos ++] = i.second;
while (last < i.first) {
replacementSeq[pos ++] = last ++;
}
last = i.first + 1;
}
return pos;
}
//----------------------
int32_t countReplacement(int32_t n, int32_t inputSeq[])
{
if (!valid(n, inputSeq)) return 0;
int flag = 1;
vector <int> v;
int mx = 0;
for (int i = 0; i < n; i ++) {
if (inputSeq[i] > n) v.push_back(inputSeq[i]);
else flag = 0;
mx = max(mx, 1ll*inputSeq[i]);
}
v.push_back(n);
sort(v.begin(), v.end());
int m = v.size();
int ans = 1;
if (flag) ans = n;
for (int i = 1; i < m; i ++) {
ans *= bp(m - i, v[i] - v[i-1] - 1);
ans %= MOD;
}/*
for (int i = n + 1; i < mx; i ++) {
if (find(v.begin(), v.end(), i) != v.end()) continue;
int pos = upper_bound(v.begin(), v.end(), i) - v.begin();
ans *= m - pos;
ans %= MOD;
}*/
return ans;
}
