#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]) {
set<int> s;
for (int i = 0; i < n; i++) {
s.insert(inputSeq[i]);
}
if ((int)s.size() != n) {
return 0;
}
int off = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] <= n) {
off = (i + n - inputSeq[i] + 1) % n;
break;
}
}
if (off != -1) {
for (int i = 0; i < n; i++) {
if (inputSeq[(i + off) % n] <= n && inputSeq[(i + off) % n] != i + 1) {
return 0;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int off = 0;
for (int i = 0; i < n; i++) {
if (gondolaSeq[i] <= n) {
off = (i + n - gondolaSeq[i] + 1) % n;
break;
}
}
vector<pair<int, int>> last;
for (int i = 0; i < n; i++) {
if (gondolaSeq[(i + off) % n] != i + 1) {
last.emplace_back(gondolaSeq[(i + off) % n], i + 1);
}
}
if (last.empty()) {
return 0;
}
sort(last.begin(), last.end());
int sz = last.size();
int prv = last.back().second;
for (int i = 0; i < sz; i++) {
for (int j = (i > 0 ? last[i - 1].first + 1 : n + 1); j < last[i].first; j++) {
replacementSeq[j - n - 1] = prv;
prv = j;
}
replacementSeq[last[i].first - n - 1] = (i < sz - 1 ? last[i].second : prv);
}
return last[sz - 1].first - n;
}
//----------------------
int countReplacement(int n, int inputSeq[]) {
return -3;
}
