#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; /** * 遅延評価で書かれているStarry Sky Tree */ template struct StarrySkyTree { typedef pair D; static const int N = 1<= N; i--) { sz[i] = 1; } for (int i = N-1; i >= 1; i--) { sz[i] = sz[i*2]+sz[i*2+1]; } } int base; void init(int b) { base = b; for (int i = 1; i < 2*N; i++) { seg[i][0] = seg[i][1] = D(0, base); } } void lzdata(int k, D x) { if (x > seg[k][0]) { swap(x, seg[k][0]); } if (x > seg[k][1]) { swap(x, seg[k][1]); } } void push(int k) { assert(1 <= k && k < N); if (seg[k][0].first >= 1) { lzdata(k*2, seg[k][0]); lzdata(k*2+1, seg[k][0]); seg[k][0] = D(0, base); } if (seg[k][1].first >= 1) { lzdata(k*2, seg[k][1]); lzdata(k*2+1, seg[k][1]); seg[k][1] = D(0, base); } } void update(int k) { assert(1 <= k && k < N); } pair get(int k) { k += N; for (int i = S; i > 0; i--) { push(k>>i); } return make_pair(seg[k][0], seg[k][1]); } void set(int a, int b, D x, int k = 1) { if (sz[k] <= a || b <= 0) return; if (a <= 0 && sz[k] <= b) { lzdata(k, x); return; } push(k); set(a, b, x, k*2); set(a-sz[k]/2, b-sz[k]/2, x, k*2+1); update(k); } }; const int MN = 100100; int a[MN]; StarrySkyTree<17> st1, st2; int main() { int n; cin >> n; vector v; for (int i = 0; i < n; i++) { cin >> a[i]; v.push_back(a[i]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (int i = 0; i < n; i++) { a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin(); } st1.init(-1); st2.init(n); int res = 0; for (int i = 0; i < n; i++) { //up auto x = st1.get(a[i]); { auto y = x.first; y.first++; res = max(res, y.first); auto u = y.second; y.second = a[i]; st2.set(0, u, y); st2.set(u+1, a[i], y); } { auto y = x.second; y.first++; res = max(res, y.first); auto u = y.second; y.second = a[i]; st2.set(0, u, y); st2.set(u+1, a[i], y); } x = st2.get(a[i]); { auto y = x.first; y.first++; res = max(res, y.first); auto u = y.second; y.second = a[i]; st1.set(a[i]+1, u, y); st1.set(u+1, n, y); } { auto y = x.second; y.first++; res = max(res, y.first); auto u = y.second; y.second = a[i]; st1.set(a[i]+1, u, y); st1.set(u+1, n, y); } } if (res <= 2) res = 0; cout << res << endl; return 0; }