#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
#ifdef B01
#include "../deb.h"
#else
#define deb(...)
#endif
const int md = 1000000009;
inline int mul(int a, int b) {
return (int) ((long long) a * b % md);
}
int valid(int n, int p[]) {
{
vector<int> d(n);
for (int i = 0; i < n; i++) {
d[i] = p[i];
}
sort(d.begin(), d.end());
d.resize(unique(d.begin(), d.end()) - d.begin());
if ((int) d.size() != n) {
return 0;
}
}
vector<int> a(n);
int s = (int) (min_element(p, p + n) - p);
if (p[s] > n) {
return 1;
}
for (int i = 0; i < n; i++) {
a[(i + p[s] - 1) % n] = p[(s + i) % n];
}
vector<int> b;
for (int i = 0; i < n; i++) {
if (a[i] <= n && a[i] != i + 1) {
return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int p[], int res[]) {
int mxi = (int) (max_element(p, p + n) - p);
int m = p[mxi] - n;
vector<int> a(n);
int s = (int) (min_element(p, p + n) - p);
if (p[s] <= n) {
for (int i = 0; i < n; i++) {
a[(i + p[s] - 1) % n] = p[(s + i) % n];
}
} else {
for (int i = 0; i < n; i++) {
a[i] = p[i];
}
}
mxi = (int) (max_element(a.begin(), a.end()) - a.begin());
vector<int> at(a[mxi] + 1, -1);
for (int i = 0; i < n; i++) {
if (a[i] > n) {
at[a[i]] = i + 1;
}
}
at[a[mxi]] = -1;
mxi++;
for (int i = 0; i < m; i++) {
int v = n + i + 1;
if (at[v] == -1) {
res[i] = mxi;
mxi = v;
} else {
res[i] = at[v];
}
}
return m;
}
//----------------------
int countReplacement(int n, int p[]) {
if (!valid(n, p)) {
return 0;
}
int m = *max_element(p, p + n) - n;
if (m == 0) {
return 1;
}
vector<int> a(n);
for (int i = 0; i < n; i++) {
a[i] = p[i];
}
sort(a.begin(), a.end());
int ans = 1;
for (int i = 0; i < m; i++) {
int v = n + i + 1;
auto it = lower_bound(a.begin(), a.end(), v);
if (*it == v) {
continue;
}
assert(it == upper_bound(a.begin(), a.end(), v));
ans = mul(ans, (int) (a.end() - it));
}
return ans;
}
