#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){ if (a[i - 1] == n){ v.push_back({1, a[i]}); a[i] = 1; } else{ v.push_back({a[i - 1] + 1, a[i]}); a[i] = a[i - 1] + 1; } } } for (int i = 0; i < st; ++i){ if (a[i] > n){ if (a[(i - 1) % n] == n){ v.push_back({1, a[i]}); a[i] = 1; } else{ v.push_back({a[(i - 1) % n] + 1, a[i]}); a[i] = a[(i - 1) % n] + 1; } } } sort(v.begin(), v.end(), [](pair<int, int> x, pair<int, int> y){ return x.second < y.second; }); for (auto [first, second] : v){ while (first != second){ replacementSeq[opt] = first; opt++; first = ++cur; } } return opt; } int countReplacement(int n, int inputSeq[]){ return 0; }