#include "gondola.h" #include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 9; int valid(int n, int a[]){ map<int, bool> exist; int app = -1; for (int i = 0; i < n; ++i){ if (exist[a[i]]) return false; exist[a[i]] = true; if (a[i] <= n && app == -1) app = i; } if (app == -1) return 1; for (int i = 1; i < n; ++i){ int idx = (app + i) % n; int expect = (a[app] + i - 1) % n + 1; if (a[idx] <= n && a[idx] != expect) return 0; } return 1; } int replacement(int n, int a[], int replacementSeq[]){ int opt = 0, cur = n, st = -1; vector<pair<int, int>> v; for (int i = 0; i < n; ++i){ if (a[i] <= n && st == -1) st = i; } if (st == -1){ st = 0; v.push_back({1, a[0]}); a[0] = 1; } for (int i = st + 1; i < n; ++i){ if (a[i] > n){ v.push_back({a[(i - 1 + n) % n] % n + 1, a[i]}); a[i] = a[(i - 1 + n) % n] % n + 1; } } for (int i = 0; i < st; ++i){ if (a[i] > n){ v.push_back({a[(i - 1 + n) % n] % n + 1, a[i]}); a[i] = a[(i - 1 + n) % n] % n + 1; } } sort(v.begin(), v.end(), [](const pair<int, int>& x, const pair<int, int>& y){ return x.second < y.second; }); for (int i = 0; i < v.size(); ++i){ int first = v[i].first, second = v[i].second; while (first < second){ replacementSeq[opt] = first; opt++; first = ++cur; } } 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 /= 2; } return res; } int countReplacement(int n, int a[]){ int st = -1; vector<int> v; for (int i = 0; i < n; ++i) if (a[i] <= n && st == -1) st = i; for (int i = 0; i < n; ++i) if (a[i] > n) v.push_back(a[i]); if (valid(n, a) == 0) return 0; sort(v.begin(), v.end()); int cnt = v.size(), cur = n; long long res = 1; for (int x : v){ res = res * binpow(1LL * cnt, (long long)(x - 1 - cur)) % mod; cur = x; cnt--; } if (st == -1) res = 1LL * res * (long long) n % mod; return res; }