#include "gondola.h"
#include "bits/stdc++.h"
using namespace std;
bool is_unique(int n, int arr[]){
set<int> s;
for (int i = 0; i < n; i++){
if (s.count(arr[i]))
return false;
s.insert(arr[i]);
}
return true;
}
vector<int> beginning(int n, int pos, int value){
vector<int> arr(n);
for (int i = 0; i < n; i++){
arr[pos] = value+1;
pos = (pos+1)%n;
value = (value+1)%n;
}
return arr;
}
int valid(int n, int arr[]){
if (!is_unique(n, arr))
return false;
int pos = -1;
for (int i = 0; i < n; i++)
if (arr[i] <= n)
pos = i;
if (pos == -1)
return 1;
vector<int> original = beginning(n, pos, arr[pos]-1);
for (int i = 0; i < n; i++)
if (arr[i] <= n and arr[i] != original[i])
return 0;
return 1;
}
//----------------------
int replacement(int n, int arr[], int answer[]){
assert(valid(n, arr));
int max_value = 0, pos = -1;
int min_value = INT_MAX;
for (int i = 0; i < n; i++){
max_value = max(max_value, arr[i]);
min_value = min(min_value, arr[i]);
if (arr[i] <= n)
pos = i;
}
if (max_value <= n)
return 0;
vector<int> original(n);
for (int i = 0; i < n; i++)
original[i] = i+1;
if (min_value <= n)
original = beginning(n, pos, arr[pos]-1);
vector<int> idx;
for (int i = 0; i < n; i++)
if (arr[i] > n)
idx.push_back(i);
sort(idx.begin(), idx.end(), [&](int x, int y){
return (arr[x] < arr[y]);
});
int position = 0, last = n+1;
for (int i = 0; i < int(idx.size()); i++){
answer[position++] = original[idx[i]];
while (last < arr[idx[i]])
answer[position++] = last++;
last += 1;
}
return position;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
