#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 1e5 + 1;
#include "gondola.h"
int valid(int n, int a[]){
for(int i = 0; i < n; i++){
if(a[i] <= n){
int j = (i + 1) % n, o = a[i] % n + 1;
while(j != i){
if(a[j] <= n && a[j] != o)return 0;
j = (j + 1) % n;
o = o % n + 1;
}
return 1;
}
}
return 1;
}
int replacement(int n, int a[], int out[]){
pii b[n];
for(int i = 0; i < n; i++){
if(a[i] <= n){
int x = a[i] % n + 1, j = (i + 1) % n, o = 1;
while(j != i){
b[o] = {a[j], x};
x = x % n + 1;
j = (j + 1) % n;
o++;
}
break;
}
else if(i == n - 1){
for(int j = 0; j < n; j++)b[j] = {a[j], j + 1};
}
}
sort(b, b + n);
int x = b[n - 1].ff - n;
for(int i = n + 1, j = 0, o = 0; j < n; j++){
if(b[j].ff == b[j].ss)continue;
while(b[j].ff != b[j].ss){
out[o++] = b[j].ss;
b[j].ss = i;
i++;
}
}
return x;
}
int countReplacement(int n, int a[]){
if(!valid(n, a)){
return 0;
}
return 1;
}
//void solve() {
//int n;
//cin >> n;
//int a[n];
//for(int i = 0; i < n; i++){
//cin >> a[i];
//}
//int out[1000];
//int sz = replacement(n, a, out);
//cout << sz << ' ';
//for(int j = 0; j < sz; j++)cout << out[j] << ' ';
//}
//int main() {
//ios_base::sync_with_stdio(0);
//cin.tie(0);
//int times = 1;
////cin >> times;
//for(int i = 1; i <= times; i++) {
//solve();
//}
//return 0;
//}
