#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MOD = 1e9+9;
void rotate(int k, vector<int> &a) {
vector<int> b = a;
int n = a.size();
for (int i=0; i<n; i++) {
b[(i+k)%n] = a[i];
}
a = b;
}
void shift(vector<int> &a) {
int n = a.size();
int mn = a[0];
for (int i=0; i<n; i++) {
mn = min(mn, a[i]);
}
int idx=-1;
for (int i=0; i<n; i++) {
if (a[i]==mn) {
idx = i;
break;
}
}
int k;
if (mn-1<idx) {
//mn-1 es el indice donde deberia estar
k = n-(idx+1)+mn;
}
else {
k = mn-1-idx;
}
//cout << k << " " << mn << "\n";
rotate(k, a);
}
int valid(int n, int A[]) {
vector<int> bf, after, a(n);
for (int i=0; i<n; i++) {
a[i] = A[i];
}
map<int, int> mp;
int mn = a[0];
for (int i=0; i<n; i++) {
mp[a[i]]++;
mn = min(mn, a[i]);
}
for (auto [x, val] : mp) {
if (val>=2) {
return 0;
}
}
if (mn > n) return 1;
int idx=-1;
for (int i=0; i<n; i++) {
if (a[i]==mn) {
idx = i;
break;
}
}
int k;
if (mn-1<idx) {
//mn-1 es el indice donde deberia estar
k = n-(idx+1)+mn;
}
else {
k = mn-1-idx;
}
//cout << k << " " << mn << "\n";
rotate(k, a);
for (int i=0; i<n; i++) {
//cout << a[i] << " ";
if (a[i]>n) continue;
if (a[i] != i+1) return 0;
}
return 1;
}
int replacement(int n, int A[], int replacementSeq[]) {
vector<int> a(n);
for (int i=0; i<n; i++) {
a[i] = A[i];
}
int mn = a[0];
for (int i=0; i<n; i++) {
mn = min(mn, a[i]);
}
int idx=-1;
for (int i=0; i<n; i++) {
if (a[i]==mn) {
idx = i;
break;
}
}
int k;
if (mn-1<idx) {
//mn-1 es el indice donde deberia estar
k = n-(idx+1)+mn;
}
else {
k = mn-1-idx;
}
//cout << k << " " << mn << "\n";
rotate(k, a);
//Rotado jiji
vector<pii> b;
for (int i=0; i<n; i++) {
if (a[i] <= n) continue;
b.push_back({a[i], i+1});
}
sort(b.begin(), b.end());
int last = n+1;
int m = b.size();
int j=0;
for (int i=0; i<m; i++) {
replacementSeq[j] = b[i].second;
j++;
while (last<b[i].first) {
replacementSeq[j] = last;
j++;
last++;
}
last = b[i].first+1;
}
return j;
}
int countReplacement(int n, int A[]) {
bool can = valid(n, A);
if (!can) return 0;
vector<int> a(n);
for (int i=0; i<n; i++) {
a[i] = A[i];
}
int mn = a[0];
for (int i=0; i<n; i++) {
mn = min(mn, a[i]);
}
int idx=-1;
for (int i=0; i<n; i++) {
if (a[i]==mn) {
idx = i;
break;
}
}
int k;
if (mn-1<idx) {
//mn-1 es el indice donde deberia estar
k = n-(idx+1)+mn;
}
else {
k = mn-1-idx;
}
//cout << k << " " << mn << "\n";
rotate(k, a);
vector<int> b(n);
map<int, int> mp;
for (int i=0; i<n; i++) {
b[i] = i+1;
mp[i+1] = i;
}
int cnt=0;
for (int i=1; i<=n; i++) {
for (int j=1; j<=n+1; j++) {
for (int k=1; k<=n+2; k++) {
//Se rompieron i, j, k en orden
if (i==j || j==k || k==i) continue;
vector<int> c = b;
mp[n+1] = mp[i];
mp[n+2] = mp[j];
mp[n+3] = mp[k];
b[mp[n+1]] = n+1;
b[mp[n+2]] = n+2;
b[mp[n+3]] = n+3;
//int old = cnt;
shift(b);
if (a==b) cnt++;
//cout << i << " " << j << " " << k << " " << old << " " << cnt << endl;
cnt %= MOD;
b = c;
}
}
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=n+1; j++) {
//Se rompieron i, j en orden
if (i==j) continue;
vector<int> c = b;
mp[n+1] = mp[i];
mp[n+2] = mp[j];
b[mp[n+1]] = n+1;
b[mp[n+2]] = n+2;
//int old = cnt;
shift(b);
if (a==b) cnt++;
//cout << i << " " << j << " " << old << " " << cnt << endl;
cnt %= MOD;
b = c;
}
}
for (int i=1; i<=n; i++) {
vector<int> c = b;
mp[n+1] = mp[i];
b[mp[n+1]] = n+1;
//int old = cnt;
shift(b);
if (a==b) cnt++;
//cout << i << " " << old << " " << cnt << endl;
cnt %= MOD;
b = c;
}
return cnt;
}
