#include<bits/stdc++.h>
#include<gondola.h>
#define maxn 250005
#define MOD 1000000009
#define pii pair<int,int>
using namespace std;
int b[maxn];
int valid(int n, int a[])
{
int minn=0;
for(int i=1;i<n;i++)if(a[i]<a[minn])minn=i;
for(int i=0;i<n;i++)b[i]=a[(i+minn)%n];
sort(a,a+n);
for(int i=0;i<n-1;i++)if(a[i]==a[i+1])return 0;
if(b[0]>n)return 1;
int pre=0;
for(int i=1;i<n;i++)
{
if(b[i]<=n)
{
if(b[i]-b[pre]!=i-pre)return 0;
pre=i;
}
}
return 1;
}
vector<pii>v;
int replacement(int n, int g[], int r[])
{
if(!valid(n,g))return -1;
int s=b[0];
for(int i=0;i<n;i++)if(b[i]>n)
{
int br=(s+i)%n;if(br==0)br=n;
v.push_back({b[i],br});
}
sort(v.begin(),v.end());
int len=v.size();
if(len==0)
{
return 0;
}
int duz=0;
for(int i=0;i<len;i++)
{
r[duz]=v[i].second;duz++;
int pre=n;
if(i!=0)pre=v[i-1].first;
for(int j=pre+1;j<v[i].first;j++)
{
r[duz]=j;
duz++;
}
}
return v[len-1].first-n;
}
long long ste(int x,int y)
{
if(y==0)return 1;
if(y%2==1)return (ste(x,y-1)*x)%MOD;
long long res=ste(x,y/2);
return (res*res)%MOD;
}
vector<int>br;
int countReplacement(int n, int a[])
{
if(!valid(n,a))return 0;
for(int i=0;i<n;i++)if(b[i]>n)br.push_back(b[i]);
sort(br.begin(),br.end());
long long sol=1;
int len=br.size();
for(int i=0;i<len;i++)
{
int pre=n;
if(i!=0)pre=br[i-1];
sol*=ste(len-i,br[i]-pre-1);
sol%=MOD;
}
if(len==n)
{
sol*=n;
sol%=MOD;
}
return sol;
}
