#include "gondola.h"
#include <vector>
#include <algorithm>
using namespace std;
int valid(int n, int inputSeq[]) {
vector<int>vec(250009, 0);
for (int i = 0; i < n; i++) vec[inputSeq[i]]++;
for (int i = 0; i <= 250000; i++) { if (vec[i] >= 2) return 0; }
for (int i = 0; i < n; i++) { if (inputSeq[i] > n) inputSeq[i] = -1; }
int v = -1;
for (int i = 0; i < n; i++) {
if (inputSeq[i] != -1) {
int z = (inputSeq[i] - i + n) % n;
if (v == -1) v = z;
else if (v != z) return 0;
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
vector<int>vec(250009, -1);
int r = -1, maxn = 0;
for (int i = 0; i < n; i++) {
maxn = max(maxn, gondolaSeq[i]); vec[gondolaSeq[i]] = i;
if (gondolaSeq[i] > n) continue;
if (r == -1) r = (gondolaSeq[i] - i + n) % n;
}
if (r == -1) r = 1;
vector<int>vec2(n, 0); for (int i = 0; i < n; i++) vec2[i] = gondolaSeq[i];
for (int i = 0; i < n; i++) { gondolaSeq[i] = (r + i) % n; if (gondolaSeq[i] == 0) gondolaSeq[i] = n; }
int cnt = 0;
for (int i = n + 1; i <= maxn; i++) {
if (vec[i] == -1) {
while (gondolaSeq[cnt] == vec2[cnt]) cnt++;
replacementSeq[i - n - 1] = gondolaSeq[cnt];
gondolaSeq[cnt] = i;
}
else {
replacementSeq[i - n - 1] = gondolaSeq[vec[i]];
gondolaSeq[vec[i]] = i;
}
}
return maxn - n;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
