#include <bits/stdc++.h> using namespace std; using ll = long long; using pi = pair<int, int>; using vi = vector<int>; using vpi = vector<pi>; using vl = vector<ll>; #ifdef LOCAL #define dbg(x) x #else #define dbg(x) 0 #endif int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vl v(n); ll mx = 0; for (auto &i : v) { cin >> i; mx = max(mx, i); } int mco = 0; ll l = 0, r = mx; // O(n * log h) auto calc = [&](int h) { int last = -1; int co = 0; for (int i = 0; i < n; i++) { if (v[i] > h) { if (last == -1) co++; last = i; } else last = -1; } dbg(cout << h << ',' << co << '\n'); return co; }; while (l<=r) { ll d = (r - l) / 3; ll m1 = l + d, m2 = 2 * d + l; int d1=calc(m1), d2=calc(m2); mco=max(mco, max(d1,d2)); if (d1>d2) r=m2-1; else l=m1+1; } cout << mco << '\n'; dbg({ for(int h=0;h<=mx;h++) { mco=max(mco, calc(h)); } cout << mco << '\n'; }); }