# include <bits/stdc++.h>
# include <gondola.h>
using namespace std;
long long n,mp[300005],idx,a[300005],b[300005],x1,x22,x2,num,x11,mx,ans[300005],cnt,anss,raod;
pair <long long , long long > x;
long long y;
multiset <pair <long long , long long > > ms;
vector <long long> v;
long long mod=1e9+9;
int valid(int n , int a[])
{
//cin>>n;
idx=-1;
for (int i=0; i<n; i++)
{
// cin>>a[i];
if (mp[a[i]]) y=1;
mp[a[i]]=1;
if (a[i]<=n) idx=i;
}
if (y==1)
{
return 0;
}
if (idx==-1)
{
return 1;
}
num=a[idx];
for (int i=idx+1; i<n; i++)
{
num++;
if (num==n+1) num=1;
if (a[i]<=n && a[i]!=num)
{
return 0;
}
}
for (int i=0; i<idx; i++)
{
num++;
if (num==n+1) num=1;
if (a[i]<=n && a[i]!=num)
{
return 0;
}
}
return 1;
}
int replacement(int n, int a[], int ans[])
{
idx=-1;
for (int i=0; i<n; i++)
{
mp[a[i]]=1;
if (a[i]<=n) idx=i;
}
if (idx==-1)
{
for (int i=0; i<n; i++)
b[i]=i+1;
for (int i=0; i<n; i++)
{
ms.insert({a[i],b[i]});
}
x2=n;
while (ms.size())
{
x=*ms.begin();
x11=x.first;
x22=x.second;
if (x11!=x22)
{
ans[cnt]=x22;
cnt++;
x2++;
}
else
{
ms.erase(ms.find({x11,x22}));
continue;
}
while (x11>x2)
{
ans[cnt]=x2;
cnt++;
x2++;
}
x2=x11;
ms.erase(ms.find({x11,x22}));
}
}
else
{
b[idx]=a[idx];
num=a[idx];
for(int i=idx+1; i<n; i++)
{
num++;
if (num==n+1) num=1;
b[i]=num;
}
for (int i=0; i<n; i++)
{
num++;
if (num==n+1) num=1;
b[i]=num;
}
for (int i=0; i<n; i++)
{
ms.insert({a[i],b[i]});
}
x2=n;
while (ms.size())
{
x=*ms.begin();
x11=x.first;
x22=x.second;
if (x11!=x22)
{
ans[cnt]=x22;
cnt++;
x2++;
}
else
{
ms.erase(ms.find({x11,x22}));
continue;
}
while (x11>x2)
{
ans[cnt]=x2;
cnt++;
x2++;
}
x2=x11;
ms.erase(ms.find({x11,x22}));
}
}
return cnt;
}
long long f_p(long long base, long long power)
{
long long result = 1;
while(power>0)
{
if(power%2==1)
{
result=(result*base)%mod;
}
base=(base*base)%mod;
power=power/2;
}
return result;
}
int countReplacement(int n, int a[])
{
idx=-1;
for (int i=0; i<n; i++)
{
if (mp[a[i]]) y=1;
mp[a[i]]=1;
if (a[i]<=n) idx=i;
}
if (y==1)
{
return 0;
}
if (idx!=-1)
{
num=a[idx];
for (int i=idx+1; i<n; i++)
{
num++;
if (num==n+1) num=1;
if (a[i]<=n && a[i]!=num)
{
return 0;
}
}
for (int i=0; i<idx; i++)
{
num++;
if (num==n+1) num=1;
if (a[i]<=n && a[i]!=num)
{
return 0;
}
}
}
for (int i=0; i<n; i++)
{
if (a[i]>n) v.push_back(a[i]);
}
sort(v.begin(), v.end());
anss=1;
if (v.size()==n) anss=n;
raod=v.size();
anss*=f_p(raod, v[0]-n-1);
anss%=mod;
for (int i=1; i<v.size(); i++)
{
raod--;
anss*=f_p(raod,v[i]-v[i-1]-1);
anss%=mod;
}
return anss;
}
