#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
int mini = n + 10, id = 0;
map<int, bool> marc;
for(int i = 0; i < n; i++){
if(marc[inputSeq[i]]) return 0;
if(inputSeq[i] < mini) mini = inputSeq[i], id = i;
marc[inputSeq[i]] = 1;
}
if(mini >= n) return 0;
for(int i = 0; i < n; i++){
if(inputSeq[(id + i) % n] <= n && inputSeq[(id + i) % n] != mini) return 0;
mini++;
if(mini > n) mini = 1;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int ini[n];
int mini = 250001, id = 0;
vector<pair<int, int> > ord;
for(int i = 0; i < n; i++){
ord.push_back(make_pair(gondolaSeq[i], i));
if(gondolaSeq[i] < mini) mini = gondolaSeq[i], id = i;
}
if(mini > n) mini = 1, id = 0;
for(int i = 0; i < n; i++){
ini[(i + id) % n] = mini;
mini++;
if(mini > n) mini = 1;
}
int cnt = 0;
int removeNow = n + 1;
sort(ord.begin(), ord.end());
for(int i = 0; i < n; i++){
if(ord[i].first <= n) continue;
replacementSeq[cnt++] = ini[ord[i].second];
while(removeNow != ord[i].first)
replacementSeq[cnt++] = removeNow++;
}
return cnt;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
