#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long
int valid(int n, int inputSeq[]){
vector<ll> v(n);
ll ssf = (ll) pow(10, 10);
int si;
unordered_set<int> us;
for (int i=0; i<n; i++){
if (us.find(inputSeq[i]) != us.end()) return 0;
us.insert(inputSeq[i]);
if (inputSeq[i] < ssf){
ssf = inputSeq[i];
si = i;
}
}
if (ssf > n) return 1;
for (int i=0; i<n; i++){
v[(ssf+i-1)%n] = inputSeq[(si+i)%n];
if (v[(ssf+i-1)%n] <= n && v[(ssf+i-1)%n] != i+1) return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
vector<ll> v(n);
ll ssf = (ll) pow(10, 10);
int si;
for (int i=0; i<n; i++){
if (gondolaSeq[i] < ssf){
ssf = gondolaSeq[i];
si = i;
}
}
if (ssf > n){
ssf = 1;
si = 0;
}
priority_queue<pair<int,int>> pq;
for (int i=0; i<n; i++){
v[(ssf+i-1)%n] = gondolaSeq[(si+i)%n];
if (v[(ssf+i-1)%n] > n) pq.push({-v[(ssf+i-1)%n], (ssf+i-1)%n});
}
int cur = n+1;
while (!pq.empty()){
int x = -pq.top().first, i = pq.top().second;
pq.pop();
bool nw = true;
while (cur <= x){
if (nw) replacementSeq[cur-n-1] = i+1;
else replacementSeq[cur-n-1] = cur-1;
nw = false;
cur++;
}
}
return cur-n-1;
}
//----------------------
int countReplacement(int n, int inputSeq[]){
return -3;
}
