#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int max_sub_1 = 2.5e5 + 5;
bool seen_sub_1[max_sub_1] = { 0 };
int valid(int n, int inputSeq[])
{
auto it = min_element(inputSeq, inputSeq + n);
int val = *it, pos = it - inputSeq;
int start_pos = pos;
while (pos != start_pos || val == *it)
{
if (inputSeq[pos] == val)
{
val++, pos++;
if (pos >= n) pos -= n;
val = min(val, n);
continue;
}
if (inputSeq[pos] > n)
{
if (seen_sub_1[inputSeq[pos]]) return 0;
seen_sub_1[inputSeq[pos]] = true;
val++, pos++;
if (pos >= n) pos -= n;
val = min(val, n);
continue;
}
return 0;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int min_val, min_pos;
auto min_it = min_element(gondolaSeq, gondolaSeq + n);
min_val = *min_it, min_pos = min_it - gondolaSeq;
vector <pii> numbers;
int val = min_val, pos = min_pos;
if (val > n) val = 1;
int replacement_pos = 0;
bool start = true;
while (pos != min_pos || start)
{
start = false;
if (gondolaSeq[pos] == val)
{
pos++, val++;
if (pos >= n) pos -= n;
if (val > n) val -= n;
continue;
}
if (gondolaSeq[pos] > n)
{
numbers.emplace_back(pii(gondolaSeq[pos], val));
pos++, val++;
if (pos >= n) pos -= n;
if (val > n) val -= n;
continue;
}
abort();
}
if (numbers.empty()) return 0;
sort(numbers.begin(), numbers.end());
int last_val = n;
for (const pii &p : numbers)
{
replacementSeq[replacement_pos++] = p.second;
last_val++;
while (last_val < p.first) replacementSeq[replacement_pos++] = last_val++;
}
return replacement_pos;
}
int countReplacement(int n, int inputSeq[])
{
return -3;
}
