#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn = 1e5 + 20;
const int maxm = 2.5e5 + 20;
int ex[maxn] , num[maxm];
int valid(int n, int a[])
{
set<int> st;
for(int i = 0; i < n; i++)
{
a[i]--;
if(a[i] < 0)
return 0;
st.insert(a[i]);
}
int f = 1;
for(int i = 0; i < n; i++)
if(a[i] < n)
f &= (a[(i + 1) % n] >= n || a[(i + 1) % n] == (a[i] + 1) % n);
f &= (int)st.size() == n;
return f;
}
//----------------------
int replacement(int n, int a[], int res[])
{
memset(num , -1 , sizeof num);
bool f = 0;
for(int i = 0; i < n; i++)
{
a[i]--;
if(!f && a[i] < n)
{
for(int j = 0; j < n; j++)
ex[j] = ((a[i] + (j - i) + n) % n) + 1;
f = 1;
}
}
if(!f)
for(int i = 0; i < n; i++)
ex[i] = i + 1;
int m = *max_element(a , a + n);
int p = max_element(a , a + n) - a;
for(int i = 0; i < n; i++)
num[a[i]] = i;
for(int i = n; i <= m; i++)
{
if(num[i] < 0)
res[i - n] = ex[p] , ex[p] = i + 1;
else
res[i - n] = ex[num[i]] , ex[num[i]] = i + 1;
}
return m - n + 1;
}
//----------------------
const int mod = 1e9 + 9;
int bpw(int a , int b)
{
if(b <= 0)
return 1;
int x = bpw(a , b / 2);
x = 1LL * x * x % mod;
if(b&1)
x = 1LL * x * a % mod;
return x;
}
int countReplacement(int n, int a[])
{
if(!valid(n , a))
return 0;
bool f = 0;
int res = 1;
vector<int> cmp;
for(int i = 0; i < n; i++)
{
if(a[i] >= n)
cmp.pb(a[i]);
else
f = 1;
}
if(!f)
for(int i = 0; i < n; i++)
res = n;
sort(cmp.begin() , cmp.end());
int m = cmp.size() , last = n;
for(int i = 0; i < m; i++)
{
res = 1LL * res * bpw(m - i , cmp[i] - last) % mod;
last = cmp[i] + 1;
}
return res;
}
