#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int M = (int) 1e6 + 1;
const int md = (int) 1e9 + 9;
int mx;
bitset<M> vis;
int valid(int n, int inputSeq[]) {
for (int i = 0; i < n; ++i) {
if (vis[inputSeq[i]] == true) {
return false;
}
mx = max(mx, inputSeq[i]);
vis[inputSeq[i]] = true;
}
function<bool(int, int, int)> Go = [&](int id, int cur, int step) {
if (id < 0 || id >= n) {
return true;
}
if (cur == 0) cur = n;
if (cur == n + 1) cur = 1;
if (inputSeq[id] <= n && inputSeq[id] != cur) {
return false;
}
return Go(id + step, cur + step, step);
};
bool ret = true;
for (int i = 0; i < n; ++i) {
if (inputSeq[i] <= n) {
ret &= Go(i, inputSeq[i], 1);
vis[inputSeq[i]] = 0;
ret &= Go(i, inputSeq[i], -1);
break;
}
}
return ret;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
for (int i = 0; i < n; ++i) {
mx = max(mx, gondolaSeq[i]);
}
for (int i = 0; i < n; ++i) {
vis[gondolaSeq[i]] = true;
}
int ans = 0;
for (int i = 1; i <= mx; ++i) {
if (!vis[i]) {
replacementSeq[ans++] = i;
}
}
return ans;
}
//----------------------
int countReplacement(int n, int inputSeq[]) {
if (!valid(n, inputSeq)) {
return 0;
}
bool f = false;
for (int i = 0; i < n; ++i) {
if (inputSeq[i] <= n) {
f = true;
}
}
int ans = 1;
if (!f) {
ans = n;
}
int cnt = 0;
for (int i = mx; i > n; --i) {
if (vis[i]) {
cnt++;
continue;
}
ans = (long long) ans * cnt % md;
}
return ans;
}
