#include "gondola.h"
#include <vector>
#include <set>
#include <algorithm>
#include <map>
using namespace std;
int valid(int n, int inputSeq[])
{
vector<int> v;
vector<int> id(n+1,0);
set<int> s;
for (int i=0;i<n;++i) {
int cur=inputSeq[i];
if (cur>n) {
if (s.find(cur)!=s.end()) return 0;
s.insert(cur);
continue;
}
v.push_back(cur);
id[cur]=i+1;
}
sort(begin(v),end(v));
if (v.empty()) return 1;
int cur=v.back(),ja=0;
v.pop_back();
while(!v.empty()) {
int prev=v.back();
if (prev==cur) return 0;
int dist=id[prev]<id[cur]?id[cur]-id[prev]:id[cur]+n-id[prev];
if (dist!=cur-prev){
return 0;
}
if (id[prev]>id[cur]) ++ja;
cur=prev;
v.pop_back();
}
return ja<=1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int exp=-1,idx=-1;
for (int i=0;i<n;++i) {
int el=gondolaSeq[i];
if (el<=n) {
exp=el;
idx=i;
break;
}
}
map<int,int> mp;
if (exp==-1) exp=1,idx=0;
for (int i=0;i<n;++i) {
int el=gondolaSeq[i];
int cu=exp+i-idx;
cu=(cu-1)%n+1;
if (el>n) mp[el]=cu;
}
int se=n;
int m=0;
for (auto [i,j]:mp) {
replacementSeq[m++]=j;
++se;
for (se;se<i;++se) {
replacementSeq[m++]=se;
}
}
return m;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
