#include using namespace std; typedef long long ll; #define REP(i,n) for(int i=0; i #define VP vector> #define VPP vector>> #define VLL vector #define VVI vector> #define VVLL vector> #define VC vector #define VS vector #define VVC vector> #define VB vector #define VVB vector> #define fore(i,a) for(auto &i:a) typedef pair P; template using min_priority_queue = priority_queue, greater>; template bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } const int INF = 1 << 30 - 1; const ll INFL = 1LL << 60; const ll mod = 998244353; vector longest_increasing_subsequence(const vector &v) { int n = v.size(); vector dp(n, INF); int m = 0; VI res(n); for (int i = 0; i < n; i++) { *lower_bound(dp.begin(), dp.end(), v[i]) = v[i]; m = max(m, (int)(lower_bound(dp.begin(), dp.end(), v[i]) - dp.begin())); res[i] = m; } return res; } int main(){ int n; cin >> n; VI a(n); VI b(n); REP(i, n) { cin >> a[i]; b[i] = -a[i]; } VI c = longest_increasing_subsequence(a); VI d = longest_increasing_subsequence(b); reverse(ALL(a)); reverse(ALL(b)); VI cc = longest_increasing_subsequence(a); VI dd = longest_increasing_subsequence(b); reverse(ALL(cc)); reverse(ALL(dd)); int ans = 0; REP(i, n) { ans = max(ans, min(c[i], cc[i])); } REP(i, n) { ans = max(ans, min(d[i], dd[i])); } cout << ans << endl; }