#include <iostream>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>
#include<stack>
#include<ctime>
#include<queue>
#include<deque>
#include<bitset>
#include<random>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using dbl = double;
# define all(x) x.begin(), x.end()
# define rall(x) x.rbegin(), x.rend()
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma comment(linker, "/STACK:1000000000")
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
ll bpow(ll a, ll n) {
return n == 0 ? 1 : n % 2 ? bpow(a, n - 1) * a : bpow(a * a, n / 2);
}
ll bpowm(ll a, ll n, ll m) {
return n == 0 ? 1 : n % 2 ? bpowm(a, n - 1, m) * a % m : bpowm(a * a % m, n / 2, m);
}
mt19937 mt(time(0));
const int N = 1e5 + 2, inf = 1e9 + 100, mod2 = 1e9 + 7, mod = 998244353, P = 257;
const ll llinf = 1e18 + 1000;
void MinMax(ll s, ll t, ll* mn, ll* mx);
ll findGap(int t, int n) {
if (t == 1) {
vector<ll> a, b;
ll l = 0, r = llinf;
while (1) {
if (a.size() * 2 == n) break;
ll* mn,* mx;
MinMax(l, r, mn, mx);
if (a.size() * 2 + 1 == n) {
a.push_back(*mn);
break;
} else {
a.push_back(*mn);
b.push_back(*mx);
}
}
reverse(all(b));
for (auto i : b) a.push_back(i);
ll ans = 0;
for (int i = 0; i + 1 < n; ++i) ans = max(ans, a[i + 1] - a[i]);
return ans;
}
}
void solve() {
}
//signed main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
//
// //freopen("coloring.in", "r", stdin);
// //freopen("coloring.out", "w", stdout);
//
// //ld time1 = clock();
//
// int tt = 1;
// cin >> tt;
// while (tt--) {
// solve();
// cout << '\n';
// cout.flush();
// }
//
// //ld time2 = clock();
// //cerr << "\n\nTIME: " << (time2 - time1) / CLOCKS_PER_SEC;
// return 0;
//}
