#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int INF = 1e9;
int valid(int n, int arr[])
{
set<int> occ;
for(int i = 0; i < n; i++){
if(occ.count(arr[i])){
return 0;
}
occ.insert(arr[i]);
}
pii mpos = {INF,INF};
for(int i = 0; i < n; i++){
mpos = min(mpos,{arr[i],i});
}
int s = mpos.second;
int cnt = 1;
for(int i = 0; i < n; i++){
int p = (s+i)%n;
if(arr[p] < n && cnt != arr[p]){
return 0;
}
cnt++;
}
return 1;
}
//----------------------
int replacement(int n, int arr[], int ans[])
{
vector<int> original(n);
pii mpos = {INF,INF};
for(int i = 0; i < n; i++){
mpos = min(mpos,{arr[i],i});
}
if(mpos.first > n) {
iota(original.begin(),original.end(),1);
}else{
int s = mpos.second;
int cnt = mpos.first-1;
for(int i = 0; i < n; i++){
int p = (s+i)%n;
original[p] = (cnt%n)+1;
cnt++;
}
}
priority_queue<pii, vector<pii>, greater<pii>> pq;
int pt = 0;
for(int i = 0; i < n; i++){
if(arr[i] <= n) continue;
pq.push({arr[i],i});
}
int cur = n;
vector<int> order;
while(pq.size()){
int v,p;
tie(v,p) = pq.top(); pq.pop();
while(cur < v){
order.push_back(p);
cur++;
}
}
int nxt = n+1;
for(auto p : order){
ans[pt++] = original[p];
original[p] = nxt++;
}
return pt;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -1;
}
