#include<bits/stdc++.h>
#include<gondola.h>
using namespace std;
const int inf=1e9+9;
const int mod=1e9+9;
vector<int> reorder(int n, int s[]){
int small=inf; int ind=-1;
for(int i=0; i<n; i++){
if(s[i]<small){
small=s[i];
ind=i;
}
}
if(n<small){
vector<int> ans(n);
for(int i=0; i<n; i++){
ans[i]=s[i];
}
return ans;
}
int start=(n+ind-(small-1))%n;
vector<int> ans(n);
for(int i=0; i<n; i++){
ans[i]=s[(start+i)%n];
}
return ans;
}
int valid(int n, int inputSeq[]){
vector<int> s=reorder(n, inputSeq);
set<int> used;
for(int i=0; i<n; i++){
if(s[i]!=i+1){
if(s[i]<=n || used.find(s[i])!=used.end()){
return false;
}
used.insert(s[i]);
}
}
return true;
}
int maximum(vector<int>& s){
int ans=-1;
for(auto e: s){
ans=max(ans, e);
}
return ans;
}
int replacement(int n, int gondolaSeq[], int ans[]){
vector<int> s=reorder(n, gondolaSeq);
int size=maximum(s)-n;
for(int i=0; i<size; i++){
ans[i]=-1;
}
set<int> usable;
for(int i=0; i<n; i++){
if(s[i]>n){
ans[s[i]-n-1]=i;
usable.insert(i);
}
}
iota(s.begin(), s.end(), 1);
for(int i=0; i<size; i++){
if(ans[i]==-1){
int ind=*usable.begin();
ans[i]=s[ind];
s[ind]=n+i+1;
}
else{
int ind=ans[i];
usable.erase(ind);
ans[i]=s[ind];
s[ind]=n+i+1;
}
}
return size;
}
int minimum(vector<int>& s){
int ans=inf;
for(auto e: s){
ans=min(ans, e);
}
return ans;
}
long long fastpow(int a, int e){
if(e==0) return 1;
long long ans=fastpow(a, e/2);
ans=(ans*ans)%mod;
if(e%2==1){
ans*=a;
ans%=mod;
}
return ans;
}
int countReplacement(int n, int inputSeq[]){
if(!valid(n, inputSeq)) return 0;
vector<int> s=reorder(n, inputSeq);
long long ans=1ll;
int usable=0;
vector<int> b;
for(int i=0; i<n; i++){
if(s[i]>n){
usable++;
b.push_back(s[i]);
}
}
sort(b.begin(), b.end());
int l=n+1;
for(auto e: b){
ans*=fastpow(usable, e-l);
ans%=mod;
l=e+1;
}
if(minimum(s)>n){
ans*=n;
ans%=mod;
}
return ans;
}
/*signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
int s[n];
for(int i=0; i<n; i++){
cin >> s[i];
}
cout << valid(n, s) << "\n";
int rep[n*3];
int size=replacement(n, s, rep);
cout << size << "\n";
for(auto e: rep){
cout << e << " ";
}
cout << "\n";
cout << countReplacement(n, s) << "\n";
}*/
