#include "gondola.h"
#include <bits/stdc++.h>
namespace {
const int MD = 1e9 + 9;
int p[250000], cur[100000];
bool flg[250000], vis[100000];
int bpow(int a, int b) {
int res = 1;
for (; b; a = (long long) a * a % MD, b /= 2) {
if (b & 1) {
res = (long long) res * a % MD;
}
}
return res;
}
}
int valid(int n, int *a) {
std::map<int, bool> mp;
for (int i = 0; i < n; ++i) {
if (mp.count(a[i])) {
return 0;
}
mp[a[i]] = 1;
int x = a[i], y = a[(i + 1) % n];
if (x <= n && y <= n) {
--x, --y;
if ((x + 1) % n != y) {
return 0;
}
}
}
return 1;
}
int replacement(int n, int *a, int *res) {
memset(p, -1, sizeof(p));
memset(flg, 0, sizeof(flg));
memset(vis, 0, sizeof(vis));
auto fill = [&](int i, int x) {
int cnt = 0;
while (cnt++ < n) {
p[x] = i;
cur[i] = x + 1;
i = (i + 1) % n;
x = (x + 1) % n;
}
};
for (int i = 0; i < n; ++i) {
if (i == n - 1 || a[i] <= n) {
fill(i, a[i] <= n ? a[i] - 1 : 0);
break;
}
}
int ma = 0;
for (int i = 0; i < n; ++i) {
p[a[i] - 1] = i;
flg[a[i] - 1] = 1;
ma = std::max(ma, a[i]);
}
int l = 0, j = 0;
for (int i = 0; i < ma; ++i) {
if (~p[i]) {
if (i >= n) {
res[l++] = cur[p[i]];
cur[p[i]] = i + 1;
}
if (flg[i]) {
vis[p[i]] = 1;
}
} else {
while (vis[j]) {
++j;
}
res[l++] = cur[j];
cur[j] = i + 1;
}
}
return l;
}
int countReplacement(int n, int *a) {
if (!valid(n, a)) {
return 0;
}
int res = 1;
std::sort(a, a + n);
if (a[0] > n) {
res = n;
}
int lst = n + 1, cnt = n;
for (int i = 0; i < n; ++i) {
if (a[i] > n) {
res = (long long) res * bpow(cnt, a[i] - lst) % MD;
lst = a[i] + 1;
}
--cnt;
}
return res;
}
