#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[]) {
vector<bool> vis;
function<bool(int, int, int)> Go = [&](int id, int cur, int step) {
if (id < 0 || id >= n) {
return true;
}
if (vis[inputSeq[id]]) {
return false;
}
vis[inputSeq[id]] = true;
if (cur == 0) cur = n;
if (cur == n + 1) cur = 1;
if (inputSeq[id] <= n && inputSeq[id] != cur) {
return false;
}
return Go(id + step, cur + step, step);
};
int mx = 0;
for (int i = 0; i < n; ++i) {
mx = max(mx, inputSeq[i]);
}
vis.resize(mx + 1);
bool ret = true;
for (int i = 0; i < n; ++i) {
if (inputSeq[i] <= n) {
ret &= Go(i, inputSeq[i], 1);
vis[inputSeq[i]] = 0;
ret &= Go(i, inputSeq[i], -1);
break;
}
}
return ret;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
int mx = 0;
for (int i = 0; i < n; ++i) {
mx = max(mx, gondolaSeq[i]);
}
vector<bool> vis(mx + 1);
for (int i = 0; i < n; ++i) {
vis[gondolaSeq[i]] = true;
}
int ans = 0;
for (int i = 1; i <= mx; ++i) {
if (!vis[i]) {
replacementSeq[ans++] = i;
}
}
return ans;
}
//----------------------
int countReplacement(int n, int inputSeq[]) {
return -3;
}
