#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
int ind = -1;
map<int, int> mp;
for (int i = 0; i < n; i++)
{
if (mp[inputSeq[i]] == 1)
return 0;
if (inputSeq[i] <= n)
ind = i;
mp[inputSeq[i]] = 1;
}
if (ind == -1)
return 1;
for (int i = 0; i < n; i++)
{
if (inputSeq[i] > n)
continue;
if (((inputSeq[ind] - inputSeq[i] + n) % n) != ((ind - i + n) % n))
return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int ind = -1, mx = 0;
map<int, int> mp;
for (int i = 0; i < n; i++)
{
if (gondolaSeq[i] <= n)
ind = i;
mx = max(gondolaSeq[i], mx);
}
set<pair<int, int>> reps;
if (ind == -1)
{
for (int i = 1; i < n + 1; i++)
reps.insert({gondolaSeq[i - 1], i});
}
else
{
for (int i = 0; i < n; i++)
{
if (gondolaSeq[i] <= n)
continue;
int dis = 0;
if(i > ind)
dis = i - ind;
else
dis = n - ind + i;
int val = gondolaSeq[ind] + dis;
if(val > n)
val = val % n;
reps.insert({gondolaSeq[i], val});
}
}
int i = 0;
while(!reps.empty())
{
pair<int, int> cur = *reps.begin();
reps.erase(reps.begin());
replacementSeq[i] = cur.second;
i++;
cur.second = n + i;
if(cur.first != cur.second)
reps.insert(cur);
}
return i;
}
int countReplacement(int n, int inputSeq[])
{
return -3;
}
