#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
long long mod=1e9+9;
int valid(int n, int v[])
{
map<int,int>mp;
int k=1e9,x=-1;
for(int i=0;i<n;i++)
{
if(mp[v[i]]==1)return 0;
mp[v[i]]++;
if(v[i]<k)
{
x=i;
k=v[i];
}
}
if(k>n)return 1;
if(k==n)k=0;
k++;
int a=x;
x=(x+1)%n;
while(x!=a)
{
if(v[x]<=n&&v[x]!=k)return 0;
x=(x+1)%n;
if(k==n)k=0;
k++;
}
return 1;
}
int replacement(int n, int v[], int res[])
{
int k=1e9,x=-1;
for(int i=0;i<n;i++)
{
if(v[i]<k)
{
x=i;
k=v[i];
}
}
vector<pair<int,int>>res1;
if(k>n)
{
k=1;x=0;
res1.push_back({v[0],1});
}
if(k==n)k=0;
k++;
int a=x;
x=(x+1)%n;
while(x!=a)
{
if(v[x]>n)
{
res1.push_back({v[x],k});
}
x=(x+1)%n;
if(k==n)k=0;
k++;
}
sort(res1.begin(),res1.end());
int l=0;
for(int i=0;i<res1.size();i++)
{
res[l]=res1[i].second;
l++;
if(i==0)a=n+1;
else a=res1[i-1].first+1;
for(int j=a;j<res1[i].first;j++)
{
res[l]=j;
l++;
}
}
return l;
}
long long vrni(long long a,long long b)
{
long long res=1;
for(int i=0;i<31;i++)
{
if(b&(1<<i))
{
res=(res*a)%mod;
}
a=(a*a)%mod;
}
return res;
}
int countReplacement(int n, int v[])
{
if(valid(n,v)==0)return 0;
int k=1e9,x=-1;
for(int i=0;i<n;i++)
{
if(v[i]<k)
{
x=i;
k=v[i];
}
}
vector<long long int>res1;
long long res=1;
if(k>n)
{
k=1;x=0;
res1.push_back(v[0]);
res=n;
}
if(k==n)k=0;
k++;
int a=x;
x=(x+1)%n;
while(x!=a)
{
if(v[x]>n)
{
res1.push_back(v[x]);
}
x=(x+1)%n;
if(k==n)k=0;
k++;
}
sort(res1.begin(),res1.end());
long long b=res1.size(),c;
for(int i=0;i<res1.size();i++)
{
if(i==0)c=n+1;
else c=res1[i-1]+1;
res=(res*(vrni(b,res1[i]-c)))%mod;
b--;
}
return res;
}
