#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 || a.empty());
}
//----------------------
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]);
int cnt = 0;
for(int i = 0; i < a.size(); i ++ ) {
if(a[i] > a[(i+1)%a.size()]) cnt ++ ;
};
if(cnt != 1 && a.size()) 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]);
};
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;
};
};
bool rp = 0;
if(in[0] == 0) {
rp = 1;
for(int i = 0; i < n; i ++ ) {
in[i] = i+1;
};
};
//for(int i = 0; i < n; i ++ ) {
//cout << in[i] << '\n';
//};
vector<int> ps{0};
for(int i = 0; i < n; i ++ )
if(in[i] < gs[i])
ps.push_back(gs[i]-n);
long long ans = 1, mod = 1e9+9;
sort(ps.rbegin(), ps.rend());
//for(int i : ps) cout << i << ' ';
//cout << '\n';
function<long long(int,int)> bp =[&](int a, int n) {
if(n == 0) return 1ll;
long long b = bp(a, n >> 1);
if(n & 1) return b*b%mod*a %mod;
return b*b%mod;
};
for(int i = 0; i+1 < ps.size(); i ++ ) {
ans *= bp(i+1, ps[i] - ps[i+1]-1);
ans %= mod;
};
if(rp)ans = ans * n %mod;
int ans2 = ans;
return ans2;
}
