#include "gondola.h" #include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 9; bool exist[25000]; int valid(int n, int a[]){ memset(exist, false, sizeof(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 = app + 1; i < n; ++i){ if (a[i] <= n){ if (a[i] == 1 && a[i - 1] != n) return 0; if (a[i] != 1 && a[i - 1] + 1 != a[i]) return 0; } else a[i] = a[i - 1] + 1; } 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 cur = n, st = -1; long long res = 1; if (valid(n, a) == 0) return 0; 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]); sort(v.begin(), v.end()); int cnt = v.size(); for (int x : v){ res = res * binpow(cnt, x - 1 - cur) % mod; cur = x; cnt--; } if (st == -1) res = res * n % mod; return res; }