#include "gondola.h" #include <bits/stdc++.h> using namespace std; const long long mod = 1e9 + 7; 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] + 1) % n, a[i]}); a[i] = (a[(i - 1 + n) % n] + 1) % n; } } for (int i = 0; i < st; ++i){ if (a[i] > n){ v.push_back({(a[(i - 1 + n) % n] + 1) % n, a[i]}); a[i] = (a[(i - 1 + n) % n] + 1) % n; } } 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; } int countReplacement(int n, int inputSeq[]){ return 0; }