#include "gondola.h" #include <bits//stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; #define ll long long #define ld long double #define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1)) #define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1)) #define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1)) #define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1)) #define iloop_(m, h, g) for (auto i = m; i < h; i += g) #define jloop_(m, h, g) for (auto j = m; j < h; j += g) #define kloop_(m, h, g) for (auto k = m; k < h; k += g) #define lloop_(m, h, g) for (auto l = m; l < h; l += g) #define getchar_unlocked _getchar_nolock // comment before submission #define pll pair<ll, ll> #define plll pair<ll, pll> #define pllll pair<pll, pll> #define vll vector<ll> #define qll queue<ll> #define dll deque<ll> #define pqll priority_queue<ll> #define gll greater<ll> #define INF 1000000000000000 #define MOD1 1000000007 #define MOD2 998244353 #define MOD3 1000000009 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); int valid(int n, int inputSeq[]) { ll cv = -1; set<ll> st; iloop(0, n) if (inputSeq[i] <= n) { if (cv != -1 && (inputSeq[i] - i + n)%n != cv) return 0; cv = (inputSeq[i] - i + n)%n; st.insert(inputSeq[i]); } return (ll)st.size() == n; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { vector<pll> tof; ll cv = -1; iloop(0, n) { if (gondolaSeq[i] <= n) cv = (gondolaSeq[i] - i + n)%n; else tof.push_back({gondolaSeq[i], i}); } if (cv == -1) cv = 0; if (tof.size()) sort(tof.begin(), tof.end()); ll ccn = 0, un = n+1; for (auto it : tof) { ll og = (it.second + cv)%n; if (og == 0) og = n; replacementSeq[ccn] = og; ccn++; while (un < it.first) { replacementSeq[ccn] = un; ccn++; un++; } un++; } return ccn; } //---------------------- int countReplacement(int n, int inputSeq[]) { return -3; }