#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define fr first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
vector<ll> seg;
ll pot, tam;
void update(ll nod, ll x)
{
seg[nod] += x;
nod /= 2;
while (nod > 0)
{
seg[nod] += x;
nod /= 2;
}
}
ll calc(ll x, ll nod, ll act)
{
if (nod >= pot)
return nod - pot;
if (seg[nod * 2] + act >= x)
return calc(x, nod * 2, act);
return calc(x, nod * 2 + 1, seg[nod * 2] + act);
}
int sequence(int N, std::vector<int> A)
{
seg.resize(0);
pot = 1;
ll i, j, l, r;
ll ma = 0;
while (pot < (N + 1))
pot *= 2;
seg.resize(pot * 2, 0);
ll mid = N - 1;
for (i = 0; i < N - 1; i++)
{
if (A[i] > A[i + 1])
{
mid = i;
break;
}
}
map<ll, ll> ap;
for (i = 0; i < mid; i++)
{
ap[A[i]]++;
ma = max(ma, ap[A[i]]);
}
ap.clear();
for (i = mid + 1; i < N; i++)
{
ap[A[i]]++;
ma = max(ma, ap[A[i]]);
}
ap.clear();
ap[A[mid]]++;
tam = 1;
l = r = mid;
for (i = mid + 1; i < N; i++)
if (A[i] == A[mid])
{
update(A[i] + pot, 1);
ap[A[i]]++;
r = i;
tam++;
}
else
break;
for (i = mid - 1; i >= 0; i--)
if (A[i] == A[mid])
{
update(A[i] + pot, 1);
ap[A[i]]++;
l = i;
tam++;
}
else
break;
ll a = calc((tam / 2) + 1, 1, 0);
ll b = calc((tam + 1) / 2 + 1, 1, 0);
ma = max(ma, ap[a]);
ma = max(ma, ap[b]);
for (i = A[mid] - 1; i > 0; i--)
{
for (j = l - 1; j >= 0; j--)
if (A[j] == i)
{
update(A[j] + pot, 1);
ap[A[j]]++;
l = j;
tam++;
}
else
break;
for (j = mid + 1; j < N; j++)
if (A[j] == i)
{
update(A[j] + pot, 1);
ap[A[j]]++;
r = j;
tam++;
}
else
break;
a = calc((tam / 2) + 1, 1, 0);
b = calc((tam + 1) / 2 + 1, 1, 0);
ma = max(ma, ap[a]);
ma = max(ma, ap[b]);
}
return ma;
}
