#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+9)
const int mxn=2e5+5,mxn2=1e6+5;
int n,color[mxn],arr[mxn],sum[mxn2];
ll pw(ll x,ll y){
if(y==0) return 1;
ll k=pw(x,y/2);
if(y%2==0){
return (k*k)%MOD;
}
return ((k*k%MOD)*x)%MOD;
}
int valid(int n, int vr[])
{
for(int i=0;i<n;i++){
arr[i]=vr[i];
}
set<int>st;
for(int i=0;i<n;i++){
st.insert(arr[i]);
}
if(st.size()!=n) return 0;
int k=n+1,idx=0;
for(int i=0;i<n;i++){
if(arr[i]>n) continue;
if(arr[i]<k){
k=arr[i];
idx=i;
}
}
for(int i=idx;i<n;i++){
if(arr[i]>n){
arr[i]=k;
}
if(arr[i]!=k) return 0;
k++;
k%=(n+1);
if(k==0) k++;
}
for(int i=0;i<idx;i++){
if(arr[i]>n){
arr[i]=k;
}
if(arr[i]!=k) return 0;
k++;
k%=(n+1);
if(k==0) k++;
}
return 1;
}
//----------------------
int replacement(int n, int arr[], int replacementSeq[])
{
int k=0,mn=n+1,idx=0;
for(int i=0;i<n;i++){
if(arr[i]>k){
k=arr[i];
}
if(arr[i]<mn){
mn=arr[i];
idx=i;
}
}
if(mn>n){
set<pii>st;
for(int i=0;i<n;i++){
st.insert({arr[i],i+1});
}
int cnt=0;
int nxt=n;
for(auto [l,id]:st){
replacementSeq[cnt++]=id;
nxt++;
while(nxt<l){
replacementSeq[cnt++]=nxt;
nxt++;
}
}
return cnt;
}
for(int i=idx;i<n;i++){
if(arr[i]>n){
color[i]=mn;
}
else{
color[i]=arr[i];
}
mn++;
mn%=(n+1);
if(mn==0) mn++;
}
for(int i=0;i<idx;i++){
if(arr[i]>n){
color[i]=mn;
}
else{
color[i]=arr[i];
}
mn++;
mn%=(n+1);
if(mn==0) mn++;
}
set<pii>st;
for(int i=0;i<n;i++){
if(color[i]<arr[i]){
st.insert({arr[i],color[i]});
}
}
int cnt=0;
int nxt=n;
for(auto [l,id]:st){
replacementSeq[cnt++]=id;
nxt++;
while(nxt<l){
replacementSeq[cnt++]=nxt;
nxt++;
}
}
return cnt;
}
//----------------------
int countReplacement(int n, int arr[])
{
int k=valid(n,arr);
if(k==0) return k;
set<int>st;
int mx=0,mn=n+1;
for(int i=0;i<n;i++){
st.insert(arr[i]);
mx=max(arr[i],mx);
mn=min(arr[i],mn);
sum[arr[i]]=1;
}
sort(arr,arr+n);
ll ans=1;
for(int i=0;i<n;i++){
if(arr[i]<=n) continue;
if(i==0){
ll cnt=arr[i]-n-1;
ans=(ans*pw(n-i,cnt))%MOD;
}
else{
ll cnt=arr[i]-max(n,arr[i-1])-1;
ans=(ans*pw(n-i,cnt))%MOD;
}
}
if(mn>n){
ans=(ans*n)%MOD;
}
return ans;
}
