#include "gondola.h"
#include <algorithm>
#include <set>
using namespace std;
#define MAX_N 101101
#define MAX_V 250052
#define MOD 1000000009
typedef long long ll;
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;
}
//----------------------
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;
}
//----------------------
set<int> CheckSame;
ll Ans = 1;
struct SORTC{
int index;
int value;
}SortC[MAX_N];
bool operator<(SORTC X, SORTC Y) {
return X.value < Y.value;
}
ll GetPower(int x, int k) {
ll result = 1;
ll powerx = x;
while(k) {
if(k%2 == 1) {
result *= powerx;
result %= MOD;
}
powerx *= powerx;
powerx %= MOD;
k/=2;
}
return result;
}
int countReplacement(int n, int inputSeq[])
{
for(int i=0; i<n; i++) {
int now = inputSeq[i];
if(CheckSame.find(now) != CheckSame.end())
return 0;
CheckSame.insert(now);
}
int first = -1;
for(int i=0; i<n; i++) {
int now = inputSeq[i];
if(now > n) continue;
first = i;
break;
}
if(first == -1) {
Ans = n;
first = 0;
}
for(int i=0; i<n; i++) {
SortC[i].index = i;
SortC[i].value = inputSeq[i];
}
sort(SortC, SortC+n);
int last = n;
for(int i=0; i<n; i++) {
int nowvalue = SortC[i].value;
if(nowvalue < n) continue;
int count = n - i;
Ans *= GetPower(count, nowvalue - last - 1);
Ans %= MOD;
last = nowvalue;
}
return (int)Ans;
}
