#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
using ll = long long;
int valid(int n, int a[])
{
bool y = true;
for (int i = 1; y && i < n; ++i) y = (a[i] - a[i - 1] + n) % n == 1;
return y;
}
//----------------------
int replacement(int n, int a[], int ans[])
{
int org = -1;
for (int i = 0; i < n; ++i)
if (a[i] <= n)
{
int norg = (i - a[i] + 1 + n) % n;
assert (org == -1 || org == norg);
org = norg;
}
if (org == -1) org = 0;
vector < pair < int, int > > v;
for (int i = 0; i < n; ++i) if (a[i] > n) v.push_back ({ a[i], (i - org + n) % n + 1 });
sort (v.begin (), v.end ());
int i = 0;
for (auto &x : v)
{
while (x.first != x.second)
{
ans[i] = x.second;
x.second = i + n + 1;
++i;
}
}
return i;
}
//----------------------
int countReplacement(int n, int a[])
{
int org = -1;
for (int i = 0; i < n; ++i)
if (a[i] <= n)
{
int norg = (i - a[i] + 1 + n) % n;
if (org != -1 && org != norg) return 0;
org = norg;
}
bool ind = false;
if (org == -1) org = 0, ind = true;
vector < ll > v;
for (int i = 0; i < n; ++i) if (a[i] > n) v.push_back (a[i]);
sort (v.begin (), v.end ());
ll vs = v.size (), ans = 1, p = n, MOD = 1000000009;
for (auto &x : v)
{
ll m = 1;
for (int i = 0; i < x - p - 1; ++i) (m *= vs) %= MOD;
(ans *= m) %= MOD;
--vs;
p = x;
}
if (ind) (ans *= (ll) n) %= MOD;
return ans;
}
