#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int valid(int n, int inputSeq[])
{
for(int i=1;i<n;i++){
if(inputSeq[i] - inputSeq[i-1] != 1 && (inputSeq[i-1] != n || inputSeq[i] != 1))return 0;
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector <pi> stuf;
int rot = 0;
for(int i=0;i<n;i++){
if(gondolaSeq[i] <= n)rot = gondolaSeq[i] - i - 1;
}
if(rot < 0)rot += n;
for(int i=0;i<n;i++){
if(gondolaSeq[i] > n){
int tmp = i + rot + 1;
if(tmp > n)tmp -= n;
stuf.push_back({gondolaSeq[i], tmp});
}
}
sort(stuf.begin(), stuf.end());
int prv = n;
int in = 0;
for(auto [i, j] : stuf){
replacementSeq[in++] = j;
prv++;
for(int x = prv + 1; x <= i; x++)replacementSeq[in++] = x - 1;
prv = i;
}
return in;
}
//----------------------
const int mod = 1e9 + 9;
long long expo(long long a, int b){
long long ans = 1;
while(b){
if(b&1)ans *= a, ans %= mod;
a *= a, a *= mod;
b >>= 1;
}
return ans;
}
int countReplacement(int n, int inputSeq[])
{
vector <pi> stuf;
int rot = -1;
for(int i=0;i<n;i++){
if(inputSeq[i] <= n){
int tmp = inputSeq[i] - i - 1;
if(tmp < 0)tmp += n;
if(rot == -1)rot = tmp;
else if(rot != tmp)return 0;
}
}
long long ans = 1, cur = n + 1;
while(1){
int cnt = 0, cnt2 = 0;
for(int i=0;i<n;i++){
if(inputSeq[i] == cur){
cnt2++;
}
if(inputSeq[i] > cur)cnt++;
}
if(cnt2 > 1)return 0;
else if(!cnt)break;
else if(cnt2 == 1){
cur++;
continue;
}
else ans *= cnt, ans %= mod, cur++;
}
return ans;
}
