#include "gondola.h"
#include <iostream>
#include <unordered_set>
#include <set>
using namespace std;
#define M 1e9+9
int alpha = 0;
int valid(int n, int inputSeq[])
{
unordered_set <int> broken;
alpha = 0;
for(int i=0;i<n;i++){
if(inputSeq[i] < n){
alpha = inputSeq[i]-i;
break;
}
}
// cout << alpha << endl;
for(int i=0;i<n;i++){
if(inputSeq[i] > n){
if(broken.count(inputSeq[i]) != 0){
// cout << "broken duplicate" << endl;
return 0;
}
broken.insert(inputSeq[i]);
}else{
if(i<=(n-alpha)){
if(inputSeq[i] != (i+alpha)){
// cout << i << " " << inputSeq[i] << " " << (i+alpha) << endl;
return 0;
}
}else{
if(inputSeq[i] != (i-(n-alpha))){
// cout << i << " " << inputSeq[i] << " " << (i-(n-alpha)) << endl;
return 0;
}
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
set<pair<int,int>> arr;
int len = 0;
alpha = 0;
for(int i=0;i<n;i++){
if(gondolaSeq[i] <= n){
alpha = gondolaSeq[i]-i;
break;
}
}
// cout << alpha << endl;
for(int i=0;i<n;i++){
if(gondolaSeq[i] > n){
if(i<=(n-alpha)){
arr.insert({gondolaSeq[i],(i+alpha)});
}else{
arr.insert({gondolaSeq[i],(i-(n-alpha))});
}
}
}
while(arr.size() > 0){
pair<int,int> a = *arr.begin();
// cout << a.first << " " << a.second << endl;
replacementSeq[len] = a.second;
len++;
a.second = n+len;
if(a.first == a.second){
arr.erase(arr.begin());
}
}
return len;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
