#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
int valid(int n,int A[]){
int x = min_element(A,A+n)-A;
for (int i((x+1)%n),k(1);i!=x;++i%=n,++k) if (A[i]<=n&&A[x]+k!=A[i]) return 0;
set<int> S(A,A+n);
return (S.size()==n);
}
int replacement(int n,int A[],int R[]){
int x = min_element(A,A+n)-A;
vector<int> B(A,A+n);
if (A[x]<=n){
int y = x-A[x]+1;
if (y<0) y += n;
for (int i(0);i < n;++i) B[(y+i)%n] = i+1;
} else iota(B.begin(),B.end(),1);
map<int,int> M; for (int i(0);i < n;++i) M[A[i]] = i;
int y = max_element(A,A+n)-A;
for (int i(n+1);i <= A[y];++i){
if (M.contains(i)) R[i-n-1] = exchange(B[M[i]],i);
else R[i-n-1] = exchange(B[y],i);
}
return A[y]-n;
}
int countReplacement(int n, int A[]){
if (!valid(n,A)) return 0;
long long mod = 1e9+9;
auto modpow = [&](long long x,long long y) -> long long {
long long res(1);
for (;y;y>>=1,(x*=x)%=mod) if (y&1) (res*=x)%=mod;
return res;
};
vector<int> B;
for (int i(0);i < n;++i) B.emplace_back(max(A[i]-n,0));
sort(B.begin(),B.end());
long long res(1);
for (int i(1);i < n;++i) if (B[i]) (res *= modpow(n-i,B[i]-B[i-1]-1)) %= mod;
if (B[0]){
(res *= modpow(n,B[0])) %= mod;
}
return res;
}
