// progress saver
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#include "gondola.h"
int valid(int n, int seq[]) {
int pr = INT_MIN, pri = INT_MIN;
unordered_set<int> seen;
FOR(i,n) {
if (seen.find(seq[i]) != seen.end()) return 0;
seen.insert(seq[i]);
if (seq[i] <= n) {
if (pr != INT_MIN) {
if (pr <= seq[i]) {
if (seq[i] - pr != i-pri) return 0;
} else {
if (n-pr+seq[i] != i-pri) return 0;
}
}
pr = seq[i];
pri = i;
}
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
// greeedy
int mn = INT_MAX, mi = -1;
FOR(i,n) {
if (gondolaSeq[i] < mn) {mn = gondolaSeq[i]; mi = i;}
}
if (mn > n) {mn = 1; mi = 0;}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // smallest replaced final gondola is processed 1st
FOR(i,n) if (gondolaSeq[(mi + i) % n] > n) pq.push({gondolaSeq[(mi + i) % n], (mn + i - 1) % n});
int rep = n;
while(pq.size()) {
int final = pq.top().F;
int original = pq.top().S; // 0 indexed (else n%n = 0)
pq.pop();
replacementSeq[rep - n] = original + 1;
rep++;
while (rep < final) {
replacementSeq[rep - n] = rep;
rep++;
}
}
return rep - n;
}
int countReplacement(int n, int seq[]) {
if (valid(n, seq) == 0) return 0;
return -3;
}
