#include "sequence.h"
#include <bits/extc++.h>
#define int long long
#define emb emplace_back
#define pii pair <int32_t, int32_t>
#define tiii tuple <int32_t, int32_t, int32_t>
#define all(a) a.begin(), a.end()
using namespace std;
using namespace __gnu_pbds;
#define ordered_multiset tree <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>
const int N = 5e5 + 5;
const int inf = 1e18;
int n, a[N];
int32_t sequence(int32_t Nn, vector<int32_t> A) {
n = Nn;
for (int i = 0; i < n; i++) a[i + 1] = A[i];
vector <int> freql(n + 1), freqr(n + 1);
int x = 0;
for (int i = 1; i < n; i++) if (a[i] > a[i + 1]) {x = i; break;}
for (int i = 1; i <= x; i++) freql[a[i]]++;
for (int i = x + 1; i <= n; i++) freqr[a[i]]++;
int ans = max(*max_element(all(freql)), *max_element(all(freqr)));
vector <int> suf(n + 2);
for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] + freql[i] + freqr[i];
for (int i = 1; i <= n; i++) {
int cur = freql[i] + freqr[i];
int after = suf[i + 1];
int lb = max(0ll, after - cur);
int rb = cur + after;
if (lb == 0) {
ans = max(ans, cur);
continue;
}
int l = 1, r = i - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (suf[mid] >= lb && suf[mid] <= rb) {
ans = max(ans, cur);
break;
}
else if (suf[mid] < lb) l = mid + 1;
else r = mid - 1;
}
}
return ans;
// ordered_multiset ms;
// int ans = 0;
// for (int l = 1; l <= n; l++) {
// vector <int> freq(n + 1);
// int sz = 0;
// for (int r = l; r <= n; r++) {
// ms.insert(a[r]);
// freq[a[r]]++;
// ans = max(ans, freq[*ms.find_by_order((sz/2))]);
// ans = max(ans, freq[*ms.find_by_order(((sz+1)/2))]);
// if (ans == 2) return 2;
// sz++;
// }
// ms.clear();
// }
// return 1;
}
