examine

#pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

#include "bits/stdc++.h"

//#define NDEBUG
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define pii pair<int, int>
#define all(m) m.begin(), m.end()
#define rall(m) m.rbegin(), m.rend()
#define uid uniform_int_distribution
#define timeStamp() std::chrono::steady_clock::now()
#define unify(m) sort(all(m)); m.erase(unique(all(m)), m.end());
#define duration_micro(a) chrono::duration_cast<chrono::microseconds>(a).count()
#define duration_milli(a) chrono::duration_cast<chrono::milliseconds>(a).count()
#define fast cin.tie(0); cout.tie(0); cin.sync_with_stdio(0); cout.sync_with_stdio(0);
using namespace std;
using str = string;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
mt19937 rnd(timeStamp().time_since_epoch().count());
mt19937_64 rndll(timeStamp().time_since_epoch().count());
template<typename T, typename U> bool chmin(T& a, const U& b) {return (T)b < a ? a = b, 1 : 0;}
template<typename T, typename U> bool chmax(T& a, const U& b) {return (T)b > a ? a = b, 1 : 0;}
struct custom_hash {static uint64_t xs(uint64_t x) {x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);} template<typename T> size_t operator()(T x) const {static const uint64_t C = timeStamp().time_since_epoch().count(); return xs(hash<T> {}(x) + C);}};
template<typename K> using uset = unordered_set<K, custom_hash>;
template<typename K, typename V> using umap = unordered_map<K, V, custom_hash>;
template<typename T1, typename T2> ostream& operator<<(ostream& out, const pair<T1, T2>& x) {return out << x.F << ' ' << x.S;}
template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& x) {return in >> x.F >> x.S;}
template<typename T, size_t N> istream& operator>>(istream& in, array<T, N>& a) {for (auto &x : a) in >> x; return in;}
template<typename T, size_t N> ostream& operator<<(ostream& out, const array<T, N>& a) {for (size_t i = 0; i < a.size(); ++i) {out << a[i];if (i + 1 < a.size()) out << ' ';}return out;}
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for (auto& x : a) in >> x; return in;}
template<typename T> ostream& operator<<(ostream& out, const vector<T>& a) {for (size_t i = 0; i < a.size(); ++i) {out << a[i]; if (i + 1 < a.size()) out << ' ';} return out;}

template<typename I> auto array_cnt(I f, I l) {umap<typename iterator_traits<I>::value_type, int> mp; while (f != l) ++mp[*f], ++f; return mp;}
template<typename I> auto subset_sum(I f, I l) {int a = l - f; vec<typename iterator_traits<I>::value_type> o(1 << a); for (int q = 1; q < (1 << a); ++q) {const int i = __builtin_ctz(q); o[q] = *(f + i) + o[q ^ (1 << i)];} return o;}
template<typename I> vec<pii> get_segs_of_eq_elems(I first, I last) {using T = typename iterator_traits<I>::value_type; vec<pii> ans; if (first == last) return ans; int l = 0; T prev = *first; int r = 1; for (auto cit = next(first); cit != last; ++cit, ++r) {if (*cit != prev) {ans.pb({l, r - 1}); l = r;} prev = *cit;} ans.pb({l, r - 1}); return ans;}
template<typename I> int LCP(I f1, I l1, I f2, I l2) {for (int o = 0; ; ++f1, ++f2, ++o) if (f1 == l1 || f2 == l2 || *f1 != *f2) return o; return -1;}
template<typename I> int min_period(I f, I l) {int a = l - f; vec<int> m(a); for (int q = 1; q < a; ++q) {for (int w = m[q - 1]; w && !m[q]; w = m[w - 1]) {if (*(f + q) == *(f + w)) m[q] = w + 1;} m[q] += !m[q] && *(f + q) == *f;} int p = a - m.back(); return a % p ? a : p;}
template<typename I> bool is_palindrome(I f, I l) {for (--l; f < l; ++f, --l) if (*f != *l) return 0; return 1;}
str from_base_10_to_base_b(ll x, ll b) {str t; if (x == 0) t = "0"; for (; x; x /= b) t += (char)('0' + x % b); reverse(all(t)); return t;}
#define vi vec<int>
#define vl vec<ll>
#define vvi vec<vec<int>>
#define vvvi vec<vec<vec<int>>>
#define vvl vec<vec<ll>>
#define vpi vec<pii>
#define vpl vec<pll>
#define vs vec<str>
#define vvs vec<vec<str>>
const int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1};
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
template<typename T_arr> int LCP(T_arr m1, T_arr m2) {return LCP(all(m1), all(m2));}
template<typename T_arr> T_arr subset_sum(T_arr m) {return subset_sum(all(m));}
template<typename T_arr> auto array_cnt(T_arr m) {return array_cnt(all(m));}
template<typename T_arr> vec<pii> get_segs_of_eq_elems(T_arr m) {return get_segs_of_eq_elems(all(m));}
template<typename T> int sum_of_digits(T val) {int o = 0; for (; val; val /= 10) o += val % 10; return o;}
template<typename T> struct static_sum_query {vec<T> m; static_sum_query() = default; template<typename I>static_sum_query(I f, I l) {m.resize(l - f + 1); for (auto it = m.begin() + 1; f != l; ++f, ++it) {*it = *(it - 1) + *f;}} template<typename T_arr> static_sum_query(T_arr& m) {(*this) = static_sum_query(all(m));} inline T query(const int l, const int r) const {return m[r + 1] - m[l];}};
template<typename T> vec<pair<T, int>> zip_with_positions(vec<T> &m) {int a = m.size(); vec<pair<T, int>> ans(a); for (int q = 0; q < a; ++q) ans[q] = {m[q], q}; return ans;}
vec<str> split(str &s, char c, bool ignore_empty = false) {vec<str> o; str u; for (int q = 0; q < s.size(); q++) {if (s[q] == c) {if (!u.empty() || !ignore_empty) o.pb(u); u.clear();} else u += s[q];} if (!u.empty() || !ignore_empty) o.pb(u); return o;}
template<typename T> str join(vec<T> &m, str c) {str o; if constexpr(is_same<str, T>::value) {for (const T &s : m) o += s + c;} else {for (const T &s : m) o += to_string(s) + c;} if (o.size()) o.erase(o.end() - c.size(), o.end()); return o;}
vec<pii> get_reflection_points_in_rect(int a, int b, int x, int y) {assert(0 <= x && x < a); assert(0 <= y && y < b); vec<pii> res = {{x, y}}; if (x != a - x - 1) res.pb({a - x - 1, y}); if (y != a - y - 1) res.pb({x, a - y - 1}); if (x != a - x - 1 && y != a - y - 1) res.pb({a - x - 1, a - y - 1}); return res;}
vec<pii> get_rotation_points_in_square(int a, int x, int y) {assert(0 <= x && x < a); assert(0 <= y && y < a); vec<pii> res = {{x, y}}; if (a % 2 == 1 && x == a / 2 && y == a / 2) return res; res.pb({a - y - 1, x}); res.pb({a - x - 1, a - y - 1}); res.pb({y, a - x - 1}); return res;}
auto integral_binary_search_left = [](auto f, auto l, auto r) {static_assert(is_same<decltype(l), decltype(r)>::value); while (l + 1 < r) {auto md = l + (r - l) / 2; if (f(md)) l = md; else r = md;} return l;};
auto integral_tersearch_argmin = [](auto f, auto l, auto r) {static_assert(is_integral_v<decltype(l)>); static_assert(is_same_v<decltype(l), decltype(r)>); using T = decltype(l); using U = decltype(f(l)); const ld FI = 1.6180339887498948482045868343656381177203; T p1 = l + (r - l) / (FI + 1), p2 = r - (r - l) / (FI + 1); U v1 = f(p1), v2 = f(p2); while (r - l > 7) {if (v1 < v2) {r = p2; p2 = p1, v2 = v1; p1 = l + (r - l) / (FI + 1), v1 = f(p1);} else {l = p1; p1 = p2, v1 = v2; p2 = r - (r - l) / (FI + 1), v2 = f(p2);}} T best_arg = l; U best_val = f(l), prv = best_val; while (++l <= r) {U tyt = l == p1 ? v1 : l == p2 ? v2 : f(l); if (tyt > prv) break; if (chmin(best_val, tyt)) best_arg = l; prv = tyt;} return best_arg;};
bool is_prime(ll c) {if (c < 2) return 0; if (c == 2 || c == 3) return 1; if (c % 2 == 0 || c % 3 == 0) return 0; const ll gr = sqrtl(c) + 1; for (ll q = 6; q <= gr; q += 6) {if (c % (q - 1) == 0) return 0; if (c % (q + 1) == 0) return 0;} return 1;}
template<typename T> vec<vec<int>> get_cycles_of_perm(vec<T> &m, int permutation_indexation) {int a = m.size(); vec<vec<int>> ans; vec<bool> us(a); for (int q = 0; q < a; ++q) {if (us[q]) continue; vec<int> tyt; for (int w = q; !us[w]; w = m[w] - permutation_indexation) {tyt.pb(w); us[w] = 1;} ans.pb(tyt);} return ans;}
int find_closing_bracket(str &s, int i) {char op = s[i], cl = op == '(' ? ')' : op == '{' ? '}' : op == '[' ? ']' : op == '<' ? '>' : '@'; assert(cl != '@'); int dep = 1; for (int q = i + 1; q < s.size(); ++q) {dep += s[q] == op ? 1 : s[q] == cl ? -1 : 0; if (dep == 0) return q;} return -1;}
template<typename T> vec<pair<T, T>> vv_to_vp(vec<vec<T>> &m) {int a = m.size(); vec<pair<T, T>> ans(a); for (int q = 0; q < a; ++q) ans[q] = {m[q][0], m[q][1]}; return ans;}
template<const int k, typename T> vec<array<T, k>> vv_to_varr(vec<vec<T>> &m) {int a = m.size(); vec<array<T, k>> ans(a); for (int q = 0; q < a; ++q) for (int w = 0; w < k; ++w) ans[q][w] = m[q][w]; return ans;}
template<typename I> bool is_B_subseq_A(I A_beg, I A_end, I B_beg, I B_end) {for (; A_beg != A_end && B_beg != B_end; ++A_beg) if (*A_beg == *B_beg) ++B_beg; return B_beg == B_end;}
template<typename T_arr> int min_period(T_arr m) {return min_period(all(m));}
template<typename T_arr> bool is_palindrome(T_arr m) {return is_palindrome(all(m));}
template<typename T_arr> T_arr reverse(T_arr x) {reverse(all(x)); return x;}
int replace(str &s, str from, str to) {str t = from; t.pb(0); t += s; int a = t.size(); vec<int> m(a); for (int q = 1; q < a; ++q) {for (int w = m[q - 1]; w && !m[q]; w = m[w - 1]) {if (t[q] == t[w]) m[q] = w + 1;} m[q] += !m[q] && t[q] == t[0];} int szf = from.size(), lst = szf; for (int q = szf; q < t.size(); ++q) {if (m[q] == szf && q - lst >= szf) {m[q - szf + 1] = -1; lst = q;}} str ans; int o = 0; for (int q = szf + 1; q < t.size(); ++q) {if (m[q] != -1) ans += t[q]; else ans += to, q += szf - 1, ++o;} s = ans; return o;}
str from_base_10_to_base_b(str x, ll b) {return from_base_10_to_base_b(stoll(x), b);}
ll from_base_b_to_base_10(str x, ll b) {ll o = 0, pw = 1; for (int q = x.size() - 1; q >= 0; --q, pw *= b) o += (x[q] - '0') * pw; return o;}
str from_base_a_to_base_b(str x, ll a, ll b) {ll x10 = from_base_b_to_base_10(x, a); return from_base_10_to_base_b(x10, b);}
template<typename T> T binpow(T x, T k) {if (k < 0) return 0; T o = 1; for (; k; k >>= 1) {if (k & 1) o = o * x; x = x * x;} return o;}
template<typename T> T ar_prog_sum_fcl(T first, T cnt, T last) {return (first + last) * cnt / 2;}
template<typename T> T ar_prog_sum_fdc(T first, T diff, T cnt) {return (first * 2 + diff * (cnt - 1)) * cnt / 2;}
template<typename T> T ar_prog_sum_fdl(T first, T diff, T last) {return (first + last) * ((last - first) / diff + 1) / 2;}
template<typename T> T geom_prog_sum_fdl(T first, T diff, T last) {return (last * diff - first) / (diff - 1);}
template<typename T> T geom_prog_sum_fdc(T first, T diff, T cnt) {return (first * binpow(diff, cnt) - first) / (diff - 1);}
template<typename T> vec<vec<T>> transpose_matrix(vec<vec<T>> &m) {int a = m.size(), b = a ? m[0].size() : 0; vec<vec<T>> ans(b, vec<T>(a)); for (int q = 0; q < a; ++q) {for (int w = 0; w < b; ++w) {ans[w][q] = m[q][w];}} return ans;}
template<typename T> vec<vec<T>> rotate_matrix_cw(vec<vec<T>> &m) {int a = m.size(), b = a ? m[0].size() : 0; vec<vec<T>> ans(b, vec<T>(a)); for (int w = 0; w < b; ++w) for (int q = 0; q < a; ++q) ans[w][q] = m[a - 1 - q][w]; return ans;}
vec<ll> get_divisors(ll x) {vec<ll> ans1, ans2; for (ll q = 1; q * q <= x; ++q) {if (x % q == 0) {ans1.pb(q); ans2.pb(x / q);}} if (ans1.back() == ans2.back()) ans1.pop_back(); reverse(all(ans2)); for (ll i : ans2) ans1.pb(i); return ans1;}
complex<ll> str_to_cmpl_ll(str t) {int ps = t.find('+'), sgn = 1; if (ps == string::npos) {ps = t.find('-'); sgn = -1; assert(ps != string::npos);} str t1 = t.substr(0, ps), t2 = t.substr(ps + 1); assert(t2.back() == 'i'); t2.pop_back(); return {stoll(t1), stoll(t2) * sgn};}
int time_to_minutes(int h, int m) {return h * 60 + m;}
int time_to_minutes(str s) {int ps = s.find(':'); assert(ps != string::npos); return time_to_minutes(stoi(s.substr(0, ps)), stoi(s.substr(ps + 1)));}
str minutes_to_time(int m, bool h0 = true, bool m0 = true) {int h = m / 60; m %= 60; str o; if (h0) o += (h < 10 ? "0" : ""); o += to_string(h); o += ':'; if (m0) o += (m < 10 ? "0" : ""); o += to_string(m); return o;}
ll lcm(ll x, ll y) {return x / __gcd(x, y) * y;}
bool is_vowel_lowercase(char c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';}
bool is_consonant_lowercase(char c) {return !is_vowel_lowercase(c);}
uint leq_pow2(const uint x) {return 1u << __lg(x);}
ull leq_pow2ll(const ull x) {return 1ull << __lg(x);}
uint geq_pow2(const uint x) {return x & (x - 1) ? 2u << __lg(x) : x;}
ull geq_pow2ll(const ull x) {return x & (x - 1) ? 2ull << __lg(x) : x;}
ll sqd(const pll p1, const pll p2) {return (p1.F - p2.F) * (p1.F - p2.F) + (p1.S - p2.S) * (p1.S - p2.S);}
ll sqd(const ll x1, const ll y1, const ll x2, const ll y2) {return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);}
template<typename T> int sign(T x) {return x < 0 ? -1 : x > 0 ? 1 : 0;}

template<typename T>
class sparse_table {
    size_t n, K;
    vector<vector<T>> m;

    //Change, if need
    inline T merge(T x, T y) const {
        return x | y;
    }

public:
    template<typename I>
    sparse_table(I first, I last) : n(last - first), K(__lg(n) + 1), m(K) {
        for (size_t i = 0; i < K; ++i) m[i].resize(max((size_t)0, n - (1 << i) + 1));
        copy(first, last, m[0].begin());
        for (size_t i = 1; i < K; ++i) {
            for (size_t j = 0; j + (1 << i) <= n; ++j) {
                m[i][j] = merge(m[i - 1][j], m[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    template<typename T_arr>
    sparse_table(T_arr& arr) {*this = sparse_table(arr.begin(), arr.end());}

    T query(size_t l, size_t r) const {
        const int u = __lg(r - l + 1);
        return merge(m[u][l], m[u][r - (1 << u) + 1]);
    }
};

class Solution {
public:
    long long maximumOr(vector<int>& m, int k) {
        sparse_table<ll> kek(m);
        ll o = 0;
        for (int q = 0; q < m.size(); ++q) {
            ll p = q ? kek.query(0, q-1) : 0;
            ll s = q+1<m.size() ? kek.query(q+1, m.size()-1) : 0;
            ll t = (1ll*m[q]) << k;
            chmax(o, p|s|t);
        }
        return o;
    }
};

static const int __ = []() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }();

static const int __ = []() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return 0; }();

template <bool b>
struct SyncPolicy
{
    static constexpr void sync()
    {
        std::ios_base::sync_with_stdio(b);
        std::cin.tie(nullptr);
        std::cout.tie(nullptr);
    }
};

template <>
struct SyncPolicy<false>
{
    static constexpr void sync() {}
};

static const int __ = []() -> int {
    SyncPolicy<false>::sync();
    return 0;
}();


typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; typedef pair<int ,int> pii; typedef pair<ll, ll> pll; typedef double rl;
typedef pii int2; typedef tuple<int, int, int> int3; typedef tuple<int, int, int, int> int4; typedef tuple<int, int, int, int, int> int5;
typedef pll ll2; typedef tuple<ll, ll, ll> ll3; typedef tuple<ll, ll, ll, ll> ll4; typedef tuple<ll, ll, ll, ll, ll> ll5;
typedef vector<int> vi; typedef vector<pii> vii; typedef vector<ll> vll; typedef vector<pll> vll_ll; typedef vector<vi> vvi; typedef vector<vii> vvii; typedef vector<vll> vvll; typedef vector<vll_ll> vvll_ll;

#define pb push_back
#define mp make_pair
#define eb emplace_back
#define xx first
#define yy second
#define FOR(i,N) for(int i=0; i<N; i++)
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define g4(x) get<4>(x)

template<typename A> string to_string(A* ptr) { stringstream ss; ss << "0x" << std::setw(16) << std::setfill ('0') << std::hex << (uint64_t)(uintptr_t)ptr; return ss.str(); }
string to_string(char c) { return ((string)"'"+c)+ "'"; }
template <typename A, typename B> string to_string(pair<A, B> p);
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
    bool first = true; string res = "{";
	for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); }
	res += "}"; return res;
}
template <size_t N> string to_string(bitset<N> v) { string res = ""; for (size_t i = 0; i < N; i++) { res += static_cast<char>('0' + v[i]); } return res; }
template <typename A> string to_string(A v) {
	bool first = true; string res = "{";
	for (const auto &x : v) {
		if (!first) { res += ", "; }
		first = false; res += to_string(x);
	}
	res += "}"; return res;
}
template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; }
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cout << " " << to_string(H); debug_out(T...); }

#define popc __builtin_popcountll
//#define popc __builtin_popcount
//#define clz __builtin_clzll
//#define clz __builtin_clz
inline int bitLength(uint32_t val) { return 32 - __builtin_clz  (val); }
inline int bitLength(uint64_t val) { return 64 - __builtin_clzll(val); }

template<typename T> inline void domax(T& A, const T& B) { A=max(A, B); }
template<typename T> inline void domin(T& A, const T& B) { A=min(A, B); }

template<typename T>
inline T true_mod(T A, T B)
{
    assert(B>=1);
    A%=B;
    if(A<0) A+=B;
    return A;
}

template<typename T>
inline T div_down(T A, T B)
{
    return (A-true_mod(A,B))/B;
}

template<typename T>
inline T div_up(T A, T B)
{
    return div_down(A+B-1, B);
}
auto factorial = [](int n) {
    std::function<int(int)> fac = [&](int n){ return (n < 2) ? 1 : n*fac(n-1); };
    return fac(n);
};

#if 1
#define dbg(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dbg(...) 42
#endif

bool ok(ll t, int n, const vector<ll>& v) {
    ll reserve=0;

    ll s=0;
    ll can=0;

    for(ll a: v) {
        can+=t;
        s+=a;

        if(s>can) return false;
    }

    return true;
}

class Solution {
public:
    int minimizeArrayValue(vector<int>& a) {
        int n=a.size();

        ll r=0;
        ll sum=0;
        FOR(i, n) {
            sum+=a[i];
            domax(r, div_up(sum, (ll)i+1));
        }
        return r;

        /*
        vector<ll> v(n);
        FOR(i, n) v[i]=a[i];

        ll l=0, r=1e9+100;
        while(l<r) {
            ll m=(l+r+0)/2;
            if(ok(m, n, v)) r=m;
            else l=m+1;
        }

        assert(l==r);
        return (int)l;
        */
    }
};