#include "gondola.h"
#define MAX_N 101101
#define MAX_V 250052
int CheckV[MAX_V];
int valid(int n, int inputSeq[])
{
for(int i=0; i<n; i++) {
int now = inputSeq[i];
CheckV[now]++;
if(CheckV[now] > 1) return 0;
}
int first = -1;
for(int i=0; i<n; i++) {
int now = inputSeq[i];
if(now > n) continue;
first = i;
break;
}
if(first == -1) return 1;
for(int i=0; i<n; i++) {
int index = (first + i) % n;
int value = (inputSeq[first] + i - 1) % n + 1;
int now = inputSeq[index];
if(now > n) continue;
if(now != value) return 0;
}
return 1;
}
//----------------------
#include <algorithm>
using namespace std;
struct SORTR{
int index;
int value;
}SortR[MAX_N];
bool operator<(SORTR X, SORTR Y) {
return X.value < Y.value;
}
int State[MAX_N];
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int first = 0;
for(int i=0; i<n; i++) {
int now = gondolaSeq[i];
if(now > n) continue;
first = i;
break;
}
for(int i=0; i<n; i++) {
int index = (first + i) % n;
int value = (gondolaSeq[first] + i - 1) % n + 1;
State[index] = value;
SortR[i].index = i;
SortR[i].value = gondolaSeq[i];
}
sort(SortR, SortR+n);
int cnt = 0;
int now = n;
for(int i=0; i<n; i++) {
int nowindex = SortR[i].index;
int nowvalue = SortR[i].value;
if(nowvalue < n) continue;
while(State[nowindex] != nowvalue) {
replacementSeq[cnt++] = State[nowindex];
State[nowindex] = ++now;
}
}
return cnt;
}
//----------------------
int countReplacement(int n, int inputSeq[])
{
return -3;
}
