import std.conv, std.functional, std.range, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } class Info { int[2] val, bef, pos; this() { val[] = 0; bef[] = -1; pos[] = -1; } override string toString() const { return format("(%s,%s,%s; %s,%s,%s)", val[0], bef[0], pos[0], val[1], bef[1], pos[1]); } } Info mul(const(Info) p, const(Info) q) { Info ret = new Info(); int s = 0, t = 0; if (p.val[s] > q.val[t]) { ret.val[0] = p.val[s]; ret.bef[0] = p.bef[s]; ret.pos[0] = p.pos[s]; ++s; } else { ret.val[0] = q.val[t]; ret.bef[0] = q.bef[t]; ret.pos[0] = q.pos[t]; ++t; } for (; s < 2 || t < 2; ) { if (s < 2 && (t == 2 || p.val[s] > q.val[t])) { if (ret.bef[0] != p.bef[s]) { ret.val[1] = p.val[s]; ret.bef[1] = p.bef[s]; ret.pos[1] = p.pos[s]; break; } ++s; } else { if (ret.bef[0] != q.bef[t]) { ret.val[1] = q.val[t]; ret.bef[1] = q.bef[t]; ret.pos[1] = q.pos[t]; break; } ++t; } } return ret; } int segN; void update(Info[] seg, int a, Info val) { a += segN; seg[a] = mul(seg[a], val); for (; a >>= 1; ) { seg[a] = mul(seg[a << 1], seg[a << 1 | 1]); } } alias Result = Tuple!(int, "val", int, "pos"); Result rangeMax(Info[] seg, int a, int b, int key) { Result ret = Result(0, -1); void check(int c) { const s = (seg[c].bef[0] != key) ? 0 : 1; chmax(ret, Result(seg[c].val[s], seg[c].pos[s])); } for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) { if (a & 1) check(a++); if (b & 1) check(--b); } return ret; } void main() { try { for (; ; ) { const N = readInt(); auto A = new int[N]; foreach (i; 0 .. N) { A[i] = readInt(); } debug { auto brt = new int[][](N, N); foreach (i; 0 .. N) { foreach (j; 0 .. i) { if (A[j] != A[i]) { chmax(brt[i][j], 2); } foreach (k; 0 .. j) { if (((A[k] < A[j] && A[j] > A[i]) || (A[k] > A[j] && A[j] < A[i])) && A[k] != A[i]) { chmax(brt[i][j], brt[j][k] + 1); } } } } writeln("brt = "); foreach (i; 0 .. N) { writeln(i, ": ", brt[i]); } int mx; foreach (i; 0 .. N) foreach (j; 0 .. i) { chmax(mx, brt[i][j]); } writeln("brute: ", (mx < 3) ? 0 : mx); } auto as = A.dup.sort.uniq.array; const asLen = cast(int)(as.length); for (segN = 1; segN < asLen; segN <<= 1) {} auto segU = new Info[segN << 1]; auto segD = new Info[segN << 1]; segU[] = new Info(); segD[] = new Info(); int ans; foreach (i; 0 .. N) { const pos = as.lowerBound(A[i]); Info dpU = new Info(); const resD0 = segD.rangeMax(0, pos, pos); dpU.val[0] = resD0.val + 1; dpU.bef[0] = resD0.pos; dpU.pos[0] = pos; if (resD0.pos != -1) { const resD1 = max(segD.rangeMax(0, resD0.pos, pos), segD.rangeMax(resD0.pos + 1, pos, pos)); dpU.val[1] = resD1.val + 1; dpU.bef[1] = resD1.pos; dpU.pos[1] = pos; } Info dpD = new Info(); const resU0 = segU.rangeMax(pos + 1, asLen, pos); dpD.val[0] = resU0.val + 1; dpD.bef[0] = resU0.pos; dpD.pos[0] = pos; if (resU0.pos != -1) { const resU1 = max(segU.rangeMax(pos + 1, resU0.pos, pos), segU.rangeMax(resU0.pos + 1, asLen, pos)); dpD.val[1] = resU1.val + 1; dpD.bef[1] = resU1.pos; dpD.pos[1] = pos; } segU.update(pos, dpU); segD.update(pos, dpD); chmax(ans, dpU.val[0]); chmax(ans, dpD.val[0]); debug { writeln(i, ": ", pos, " ", dpU, " ", dpD); // writeln("segU = ", segU); // writeln("segD = ", segD); } } writeln((ans < 3) ? 0 : ans); } } catch (EOFException e) { } }