#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
// int inputSeq[10000];
// int replacementSeq[10000];
// int gondolaSeq[10000];
int valid(int n, int inputSeq[]){
vector<pair<int,int>>v;
set<int>s;
for(int i=0; i<n; i++){
if(inputSeq[i]<=n)v.push_back({inputSeq[i],i});
if(s.find(inputSeq[i])!=s.end()){
return false;
}
s.insert(inputSeq[i]);
}
for(int i=1; i<v.size(); i++){
//if(v[i-1]==1)continue;
if(v[i].first==1){
continue;
}
if(v[i].first-v[i-1].first==v[i].second-v[i-1].second)continue;
return false;
}
//cout<<"NEKO"<<endl;
return true;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
// for(int i=0; i<n; i++){
// cout<<gondolaSeq[i]<<" ";
// }
if(valid(n,gondolaSeq)==false){
cout<<"NYAN"<<endl;
return 0;
}
else{
vector<int>v(n,0);
for(int i=0; i<n; i++){
if(gondolaSeq[i]<=n){
v[i]=gondolaSeq[i];
}
}
for(int i=0; i<n; i++){
if(v[i]!=0){
for(int j=i+1; j<n; j++){
v[j]=v[j-1]+1;
v[j]%=(n+1);
if(v[j]==0)v[j]++;
}
break;
}
}
// for(int i=0; i<n; i++){
// cout<<v[i]<<" ";
// }
for(int i=n-1; i>=0; i--){
if(v[i]!=0){
for(int j=i+1; j<n; j++){
if(v[j]==0){
v[j]=v[j]+n+1+v[j-1]-1;
v[j]%=(n+1);
}
}
}
}
// for(int i=0; i<n; i++){
// cout<<v[i]<<" ";
// }
vector<int>bati;
map<int,int>mp;
vector<pair<int,int>>ixvi;
for(int i=0; i<n; i++){
mp[gondolaSeq[i]]++;
if(gondolaSeq[i]>n){
ixvi.push_back({gondolaSeq[i]-1,n+1});
}
}
for(int i=1; i<=n; i++){
if(mp[i]==0)bati.push_back(i);
}
for(int i=0; i<ixvi.size(); i++){
for(int j=ixvi[i].second; j<=ixvi[i].first; j++){
bati.push_back(j);
}
}
int k=0;
for(auto a:bati){
cout<<a<<" ";
replacementSeq[k]=a;
k++;
}
return bati.size();
}
//return 0;
}
long long N=1000000009;
#define ll long long
long long batuka(ll a,ll b) {
a%=N;b%=N;
long long r=1;
while(b>0){
if(b&1){
a%=N;
r=r*a;
r%=N;
}
a=a*a;
a%=N;
b/=2;
}
return r;
}
int countReplacement(int n, int inputSeq[]){
if(valid(n,inputSeq)==false){
return 0;
}
else{
vector<ll>v;
ll m=0;
ll j=n+1;
for(int i=0; i<n; i++){
if(inputSeq[i]>n){
v.push_back(inputSeq[i]);
m++;
}
}
//cout<<m<<endl;
sort(v.begin(),v.end());
long long sum=1;
if(m==n){
sum*=m;
sum%=N;
}
for(int i=0; i<v.size(); i++){
ll k=v[i]-j;
sum*=batuka(m,k);
//cout<<m<<' '<<k<<endl;
sum%=N;
m--;
j=v[i];
}
return sum%N;
}
return 0;
}
