#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
set<int> st;
for (int i=0; i<n; i++)
{
if (st.find(inputSeq[i])!=st.end()) return 0;
st.insert(inputSeq[i]);
}
int s, cnt(0);
bool can=1;
pair<int, int> mn={INT_MAX, -1};
for (int i=0; i<n; i++) mn=min(mn, {inputSeq[i], i});
if (mn.first>n) return 1;
cnt=mn.first;
s=mn.second;
for (int i=s; i<n; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
for (int i=0; i<s; i++) if (inputSeq[i]!=cnt++&&inputSeq[i]<=n) can=0;
return can;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int cnt(0), res(0);
set<pair<int, int>> s;
for (int i=0; i<n; i++) if (gondolaSeq[i]>n) s.insert({gondolaSeq[i], i});
pair<int, int> mn={INT_MAX, -1};
for (int i=0; i<n; i++) if (gondolaSeq[i]<=n) mn=min(mn, {gondolaSeq[i], i});
if (mn.first==INT_MAX) mn={1, 0};
cnt=mn.first-1;
vector<int> p(n);
//printf("%d\n", mn.second);
for (int i=mn.second; i<n; i++) p[i]=(++cnt)>n?cnt-n:cnt;
for (int i=0; i<mn.second; i++) p[i]=(++cnt)>n?cnt-n:cnt;
//for (int i=0; i<n; i++) cout<<p[i]<<' ';
//cout<<'\n';
for (auto [x, y]:s)
{
//cout<<x<<' '<<y<<'\n';
replacementSeq[res++]=p[y];
while (res+n!=x) replacementSeq[res]=res+n, res++;
}
return res;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
