#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int arr[]){
unordered_set<int>se;
bool amos=true;
deque<int>d;
int mini=INT_MAX;
int small=0;
int big=0;
for(int x=0;x<n;x++){
if(se.find(arr[x])!=se.end()) amos=false;
se.insert(arr[x]);
if(arr[x]<=n){
d.push_back(arr[x]);
mini=min(mini,arr[x]);
small++;
}
else big++;
}
//int ptr=1;
//for(int x=1;x<=n;x++){
//if(se.find(x)==se.end()){
//if(se.find(ptr+n)==se.end()) amos=false;
//ptr++;
//}
//}
if(n-small!=big) amos=false;
if(!d.empty()){
while(d.front()!=mini){
d.push_front(d.back());
d.pop_back();
}
for(int x=1;x<(int)d.size();x++){
if(d[x]<d[x-1]) amos=false;
}
}
return amos;
}
int replacement(int n, int arr[], int ans[]){
int maxi=0;
int shift=-1;
deque<int>d;
for(int x=0;x<n;x++){
maxi=max(maxi,arr[x]);
if(arr[x]<=n){
if(arr[x]>=x+1){
shift=arr[x]-(x+1);
}
else{
shift=arr[x]+n-(x+1);
}
}
d.push_back(arr[x]);
}
while(shift>0){
shift--;
d.push_front(d.back());
d.pop_back();
}
vector<pair<int,int>>v;
for(int x=0;x<n;x++){
if(d[x]>n){
v.push_back({d[x],x});
}
}
sort(v.begin(),v.end());
int index=0;
int cur=n;
for(auto it:v){
bool done=true;
while(cur<it.first){
if(done){
ans[index]=it.second+1;
done=false;
index++;
}
else{
ans[index]=cur;
index++;
}
cur++;
}
}
return maxi-n;
}
//----------------------
int countReplacement(int n, int inputSeq[]){
return 0;
}
//
