/**
* ...
*
* Time Complexity: O(n * log(n)) (not finished)
* Implementation 0.5
*/
#include <bits/stdc++.h>
#include "gondola.h"
typedef std::vector<int> vec;
vec cyc_shift(int n, int input_seq[]) {
int original = -1, original_pos = -1;
for (int k = 0; k < n && original == -1; k++) {
if (input_seq[k] <= n)
original = input_seq[k], original_pos = k;
}
vec shift(n);
int delta = (original != -1 ? original_pos + 1 - original : 0);
for (int k = 0; k < n; k++)
shift[k] = input_seq[(k + delta + n) % n];
return shift;
}
int valid(int n, int input_seq[]) {
vec shift = cyc_shift(n, input_seq);
bool ok = true;
std::set<int> appeared;
for (int k = 0; k < n && ok; k++) {
if (shift[k] <= n) {
ok &= (shift[k] == k + 1);
} else {
ok &= (appeared.find(shift[k]) == appeared.end());
appeared.emplace(shift[k]);
}
}
return ok;
}
int replacement(int n, int gondola_seq[], int replacement_seq[]) {
assert(valid(n, gondola_seq));
vec shift = cyc_shift(n, gondola_seq);
memset(replacement_seq, -1, sizeof(int) * 250000);
int repl_len = 0;
for (int k = 0; k < n; k++) {
if (shift[k] > n) {
repl_len = std::max(repl_len, shift[k] - n);
replacement_seq[shift[k] - n - 1] = k + 1;
}
}
for (int k = repl_len - 1, last = -1; k >= 0; k--) {
if (replacement_seq[k] == -1) {
replacement_seq[k] = replacement_seq[last];
replacement_seq[last] = n + k + 1;
} else {
last = k;
}
}
return repl_len;
}
int countReplacement(int n, int input_seq[]) {
return -3;
}
