#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
const int N = 3e5+1 ;
int b[N];
int valid(int n ,int* a){
set<int> el ;
for(int i=0;i<n;i++) el.insert(a[i]) ;
if(el.size()!=n) return 0 ;
bool flg= 0 ;
for(int i=0;i<n;i++){
if(a[i]>n) continue;
for(int j=i;j<=n+i;j++){
if(a[j%n]>n) {b[j%n]=((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n) ;
continue ;
}
if(a[j%n]==((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n)){
b[j%n]=((a[i]+j-i)<=n?a[i]+j-i:a[i]+j-i-n) ;
continue ;
}
return 0;
}
break ;
}
return 1 ;
}
int replacement(int n , int* a , int* ans){
valid(n,a) ;
vector<int> hey ;
for(int i=0;i<n;i++)if(a[i]>n) hey.push_back(i) ;
if(hey.size()==n){
for(int i=0;i<n;i++) b[i]=(i+1) ;
}
//for(int i=0;i<n;i++) cout << b[i] << " ";
// cout << endl ;
sort(hey.begin(),hey.end(),[&](int i ,int j){
return a[i]>a[j] ;
}) ;
int res = 0 ;
int mx = 0 ;
for(int i=0;i<n;i++) mx = max(mx,a[i]) ;
// cout << mx << endl ;
// for(int x: hey) cout << x << " ";
//cout << endl ;
for(int i=n+1;i<=mx;i++){
if(a[hey.back()]<i){
hey.pop_back();
}
ans[res++]=b[hey.back()];
b[hey.back()]=i;
}
return res;
}
int countReplacement(int n,int* a){
const int md = 1e9+9 ;
if(valid(n,a)==0) return 0 ;
#define int long long
int spots = 0 ;
for(int i=0;i<n;i++) spots+=(a[i]>n) ;
int ans = (spots==n?n:1), mx = 0 ;
for(int i=0;i<n;i++) mx = max(mx,(int)a[i]) ;
set<int> vis ;
for(int i=0;i<n;i++) if(a[i]>n)vis.insert(a[i]) ;
int last = n;
function<int(int,int)> be=[](int b ,int e){
int ans =1;
while(e){
if(e&1) ans*=b;
b*=b,e/=2;
ans%=md,b%=md ;
}
return ans;
} ;
//cout << ans << ndl ;
for(int x: vis)
(ans*=be(spots,(x-last-1)))%=md,--spots,last = x ;
// cout << last << " " << x << " " <<spots << " " << be(spots,(x-last-1)) << endl ;
#undef int
int hey = ans ;
return hey;
}
/*int main(){
int a[7] = {2, 3, 4, 9, 6, 7, 1} ;
int ans[10] ;
int n = replacement(7,a,ans);
cout << n <<endl ;
for(int i=0;i<n;i++) cout << ans[i] << " " ;
return 0 ;
}
*/
