#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000009LL;
int valid(int n, int a[]){
// không sửa a[], kiểm tra theo vòng (circular)
unordered_set<int> seen;
int st = -1;
for (int i = 0; i < n; ++i){
if (seen.count(a[i])) return 0;
seen.insert(a[i]);
if (a[i] <= n && st == -1) st = i;
}
if (st == -1) return 1; // tất cả là spare -> hợp lệ
int prev = a[st];
for (int j = 1; j < n; ++j){
int idx = (st + j) % n;
int expected = (prev % n) + 1;
if (a[idx] <= n){
if (a[idx] != expected) return 0;
prev = a[idx];
} else {
// spare: nó tương ứng với giá trị expected (tăng chuỗi)
prev = expected;
}
}
return 1;
}
int replacement(int n, int a[], int replacementSeq[]){
// tạo bản sao b[] để không sửa a[]
vector<int> b(n);
for (int i = 0; i < n; ++i) b[i] = a[i];
int st = -1;
for (int i = 0; i < n; ++i) if (b[i] <= n && st == -1) st = i;
vector<pair<int,int>> v; // (startExpected, spareLabel)
if (st == -1){
// không có gondola gốc: giả sử bắt đầu bằng 1 tại vị trí 0
st = 0;
v.push_back({1, b[0]});
b[0] = 1;
}
int prev = b[st];
for (int j = 1; j < n; ++j){
int idx = (st + j) % n;
int expected = (prev % n) + 1;
if (b[idx] > n){
v.push_back({expected, b[idx]});
b[idx] = expected; // lấp chỗ bằng expected để tiếp tục mô phỏng
prev = b[idx];
} else {
prev = b[idx];
}
}
sort(v.begin(), v.end(), [](const pair<int,int>& x, const pair<int,int>& y){
return x.second < y.second;
});
int opt = 0;
int cur = n;
for (auto &p : v){
int first = p.first; // số gondola gốc (1..n) đi hỏng ngay lúc đó
int second = p.second; // nhãn spare xuất hiện ở vị trí đó (> n)
// luôn đưa số đầu (gondola gốc) vào replacement sequence
replacementSeq[opt++] = first;
// sau đó các spare numbers (n+1 ... second-1) bị tạo trước khi spare 'second'
for (int s = cur + 1; s < second; ++s){
replacementSeq[opt++] = s;
}
if (second - 1 > cur) cur = second - 1;
}
return opt;
}
long long binpow(long long base, long long e){
long long res = 1;
while (e > 0){
if (e & 1) res = (res * base) % mod;
base = (base * base) % mod;
e >>= 1;
}
return res;
}
int countReplacement(int n, int a[]){
// không thay đổi a[] ở đây
int st = -1;
for (int i = 0; i < n; ++i) if (a[i] <= n && st == -1) st = i;
vector<int> v;
for (int i = 0; i < n; ++i) if (a[i] > n) v.push_back(a[i]);
if (!valid(n, a)) return 0;
sort(v.begin(), v.end());
long long res = 1;
int cur = n;
int cnt = (int)v.size();
for (int x : v){
long long exp = (long long)(x - 1 - cur);
if (exp > 0){
res = (res * binpow(cnt, exp)) % mod;
}
cur = x;
cnt--;
}
if (st == -1) res = (res * (long long)n) % mod;
return (int)res;
}
