#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
int valid(int n, int in[])
{
vector<int> a;
for(int i = 0; i < n; i ++ ) if(in[i] < n)a.push_back(in[i]);
set<int> st;
for(int i = 0; i < n; i ++ ) st.insert(in[i]);
if(st.size() != n) return 0;
int cnt = 0;
for(int i = 0; i < a.size(); i ++ ) {
if(a[i] > a[(i+1)%a.size()]) cnt ++ ;
};
return (cnt == 1);
}
//----------------------
int replacement(int n, int gs[], int rs[])
{
int mx = n;
for(int i = 0; i < n; i ++ ) {
mx = max(mx, gs[i]);
};
int sz = mx - n;
vector<int> us(mx+1);
for(int i = 0; i < n; i ++ ) {
us[gs[i]] = 1;
};
vector<int> in(n);
for(int i = 0; i < n; i ++ ) {
if(gs[i] <= n) {
for(int j = i - 1; j >= 0; j -- ) {
if(gs[i] - (i-j) <= 0) in[j] = gs[i] - (i-j) + n;
else in[j] = gs[i] - (i-j);
};
for(int j = i; j < n; j ++ ) {
if(gs[i] + (j-i) > n) in[j] = gs[i] + (j-i) - n;
else in[j] = gs[i] + (j-i);
};
break;
};
};
if(in[0] == 0) {
for(int i = 0; i < n; i ++ ) {
in[i] = i+1;
};
};
for(int i = 0; i < n; i ++ ) {
if(in[i] < gs[i]) {
rs[gs[i]-n-1] = in[i];
};
};
for(int i = sz-1; i >= 0; i -- ) {
if(rs[i] == 0) {
int x = rs[i+1];
rs[i+1] = n + i + 1;
rs[i] = x;
};
};
return sz;
}
//----------------------
int countReplacement(int n, int gs[])
{
vector<int> a;
for(int i = 0; i < n; i ++ ) if(gs[i] < n)a.push_back(gs[i]);
set<int> st;
for(int i = 0; i < n; i ++ ) st.insert(gs[i]);
if(st.size() != n) return 0;
int cnt = 0;
for(int i = 0; i < a.size(); i ++ ) {
if(a[i] > a[(i+1)%a.size()]) cnt ++ ;
};
if(cnt != 1) return 0;
bool o1 = 1;
for(int i = 0; i < n; i ++ ) {
if(gs[i] > n) o1 = 0;
};
if(o1) return 1;
/////////////////////////////////////////////////////////////////////
int mx = n;
for(int i = 0; i < n; i ++ ) {
mx = max(mx, gs[i]);
};
int sz = mx - n;
vector<int> us(mx+1);
for(int i = 0; i < n; i ++ ) {
us[gs[i]] = 1;
};
vector<int> in(n);
for(int i = 0; i < n; i ++ ) {
if(gs[i] <= n) {
for(int j = i - 1; j >= 0; j -- ) {
if(gs[i] - (i-j) <= 0) in[j] = gs[i] - (i-j) + n;
else in[j] = gs[i] - (i-j);
};
for(int j = i; j < n; j ++ ) {
if(gs[i] + (j-i) > n) in[j] = gs[i] + (j-i) - n;
else in[j] = gs[i] + (j-i);
};
break;
};
};
if(in[0] == 0) {
for(int i = 0; i < n; i ++ ) {
in[i] = i+1;
};
};
vector<int> rs(sz+1);
for(int i = 0; i < n; i ++ ) {
if(in[i] < gs[i]) {
rs[gs[i]-n-1] = 1;
};
};
long long ans = 1, mod = 1e9+9, mul = 0;
for(int i = sz-1; i >= 0; i -- ) {
if(rs[i]) {
mul ++ ;
continue;
};
ans *= mul;
ans %= mod;
};
int ans2 = ans;
return ans2;
}
