#include<bits/stdc++.h>
using namespace std;
#include "gondola.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define N 100005
int valid(int n, int a[]){
int i;
long long mod=1e18;
set<int> s;
for(i=0;i<n;i++){
if(s.count(a[i]))return 0;
s.insert(a[i]);
if(a[i]>n)continue;
if(mod==1e18)mod=(i-a[i]+n)%n;
else if(mod!=(i-a[i]+n)%n)return 0;
}
return 1;
}
int replacement(int n, int a[], int b[]){
int i,j,now,last,cnt;
vector<pair<int,int>> v;
for(i=0;i<n;i++)if(a[i]>n)v.push_back({a[i],i});
for(i=0;i<n;i++){
if(a[i]<=n){
now=a[i];
for(j=i+1;j<n;j++){
now++;
if(now==n+1)now=1;
a[j]=now;
}
for(j=0;j<i;j++){
now++;
if(now==n+1)now=1;
a[j]=now;
}
break;
}
}
if(i==n)for(i=0;i<n;i++)a[i]=i+1;
sort(v.begin(),v.end());
i=0;
last=n;
for(auto [now,x]:v){
cnt=now-last;
while(cnt--)b[i++]=a[x],a[x]=i+n;
last=now;
}
return i;
}
long long mod=1e9+9;
long long bp(long long a,long long b){
if(b==0)return 1;
long long temp=bp(a,b/2);
if(b%2)return temp*temp%mod*a%mod;
return temp*temp%mod;
}
int countReplacement(int n, int a[]){
int i,len,last;
long long ans=1;
vector<int> v;
if(!valid(n,a))return 0;
for(i=0;i<n;i++)if(a[i]>n)v.push_back(a[i]);
sort(v.begin(),v.end());
len=v.size();
last=n;
for(i=0;i<len;i++){
ans=ans*bp(len-i,v[i]-last-1)%mod;
last=v[i];
}
if(len==n)ans=ans*n%mod;
return ans;
}
