#include "gondola.h"
//#include "grader.cpp"
#include <set>
#include <vector>
#include <cstring>
#include <assert.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 3e5 + 5;
namespace Valid
{
bool seen[MAXN];
bool sortedL[MAXN], sortedR[MAXN];
void fillSeen(int n, int a[], int maxVal)
{
for(int i = 0;i<=maxVal;i++)
{
seen[i] = false;
}
for(int i = 0;i<n;i++)
{
seen[ a[i] ] = true;
}
}
bool check(int n, int a[], int relevant)
{
int maxVal = 0;
for(int i = 0;i<n;i++)
{
maxVal = max(maxVal, a[i]);
sortedL[i] = sortedR[i] = false;
}
for(int i = 0;i<=maxVal;i++)
{
seen[i] = false;
}
for(int i = 0;i<n;i++)
{
if(seen[ a[i] ]==true) return false;
seen[ a[i] ] = true;
}
sortedL[0] = true;
for(int i = 1;i<n;i++)
{
if(a[i]>relevant) sortedL[i] = sortedL[i-1];
else sortedL[i] = (sortedL[i-1]&(a[i-1]<a[i]));
}
sortedR[n-1] = true;
for(int i = n-2;i>=0;i--)
{
if(a[i]>relevant) sortedR[i] = sortedR[i+1];
else sortedR[i] = (sortedR[i+1]&(a[i]<a[i+1]));
}
if(sortedL[n-1]==true && (a[n-1]==n || (a[n-1]>relevant && seen[n]==false))) return true;
for(int i = 0;i<n-1;i++)
{
if(sortedL[i]==true && sortedR[i+1]==true)
{
if(a[i]>relevant || a[i+1]>relevant)
{
if((a[i]>relevant && seen[n]==false) && (a[i+1]>relevant && seen[1]==false))
{
return true;
}
}
else
{
if(a[i]==n && a[i+1]==1)
{
return true;
}
}
}
}
return false;
}
};
namespace Replacement
{
bool checkSpecial(int n, int a[])
{
for(int i = 0;i<n;i++)
{
if(a[i]<=n) return false;
}
return true;
}
//1 2 3 4
//4 1 2 3
//3 4 1 3
vector <pair <int, int>> genRaw(int n, int a[])
{
int shift = -1;
for(int i = 0;i<n;i++)
{
if(a[i]<=n)
{
if(a[i]<=i+1) shift = (i + 1) - a[i];
else shift = (n - a[i]) + (i + 1);
break;
}
}
vector <pair <int, int>> out;
for(int i = 0;i<n;i++)
{
if(a[i]>n)
{
out.push_back({a[i], (i-shift+n)%n+1});
}
}
return out;
}
vector <pair <int, int>> genRawSpecial(int n, int a[])
{
vector <pair <int, int>> out;
for(int i = 0;i<n;i++)
{
out.push_back({a[i], i+1});
}
return out;
}
vector <int> solve(int n, int a[])
{
vector <int> answer;
vector <pair <int, int>> raw;
if(checkSpecial(n, a)==false) raw = genRaw(n, a);
else raw = genRawSpecial(n, a);
int num = n + 1;
sort(raw.begin(), raw.end());
for(pair <int, int> x: raw)
{
if(num!=x.first)
{
answer.push_back(x.second);
num++;
while(num<=x.first)
{
answer.push_back(num-1);
num++;
}
}
else
{
answer.push_back(x.second);
num++;
}
}
//for(pair <int, int> x: raw) cout << x.first << " " << x.second << " || ";
//cout << '\n';
return answer;
}
};
int valid(int n, int inputSeq[])
{
return Valid::check(n, inputSeq, n);
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <int> v = Replacement::solve(n, gondolaSeq);
for(int i = 0;i<v.size();i++) replacementSeq[i] = v[i];
return v.size();
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
//1 2 3 4 5
//6 7 8 9 10
