#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
int baseline = -1;
int baselineIdx = -1;
for (int x = 0; x < n; x++){
if (inputSeq[x] <= n){
baseline = inputSeq[x];
baselineIdx = x;
}
}
unordered_set<int> hmm;
for (int x = 0; x < n; x++){
if (hmm.count(inputSeq[x]) != 0) return 0;
hmm.insert(inputSeq[x]);
}
if (baseline == -1){
return 1;
}
//baseline is supposed to be at x+1
int shiftsRight = baselineIdx+1 - baseline;
int shifted[n];
for (int x = 0; x < n; x++) {
shifted[x] = inputSeq[(x + shiftsRight + n)%n];
}
hmm.clear();
for (int x = 0; x < n; x++){
if (shifted[x] <= n && shifted[x] != x+1) return 0;
if (hmm.count(shifted[x]) != 0) return 0;
hmm.insert(shifted[x]);
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int baseline = -1;
int baselineIdx = -1;
for (int x = 0; x < n; x++){
if (gondolaSeq[x] <= n){
baseline = gondolaSeq[x];
baselineIdx = x;
}
}
int shifted[n];
if (baseline != -1){
//baseline is supposed to be at x+1
int shiftsRight = baselineIdx+1 - baseline;
for (int x = 0; x < n; x++) {
shifted[x] = gondolaSeq[(x + shiftsRight + n)%n];
}
}
else for (int x = 0; x < n; x++) shifted[x] = gondolaSeq[x];
map<int, int> hhh;
for (int x = 0; x < n; x++){
hhh[shifted[x]] = x;
}
int hmm[n];
for (int x = 0; x < n; x++) hmm[x] = x+1;
int nextRep = n+1;
vector<int> ans;
for (auto i : hhh){
int val = i.first, idx = i.second;
while (hmm[idx] < val){
ans.push_back(hmm[idx]);
hmm[idx] = nextRep;
nextRep++;
}
}
int cnt = 0;
for (int x : ans) replacementSeq[cnt] = x, cnt++;
return (int)ans.size();
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
