给定一个整数序列 $A = (a_1, a_2, \dots, a_N)$。求满足以下两个条件的最长序列 $B = (b_1, b_2, \dots, b_M)$ 的长度：

• $B$ 是 $A$ 的子序列
• 对于所有 $i$ ($1 \le i \le M - 2$)，满足 $b_i < b_{i+2}$

序列的子序列是指从原序列中删除零个或多个元素，并在不改变顺序的情况下连接剩余元素所得到的序列。

输入格式

第一行包含一个整数 $N$，表示 $A$ 中元素的个数 ($1 \le N \le 5000$)。 第二行包含 $N$ 个整数，每个整数在 $1$ 到 $N$ 之间（含 $1$ 和 $N$）。对于每个 $i$ ($1 \le i \le N$)，$a_i$ 表示 $A$ 的第 $i$ 个元素 ($1 \le a_i \le N$)。

输出格式

输出一个整数，即问题的答案。

样例

输入 1

8
1 5 7 8 6 3 4 2

输出 1

4

输入 2

8
1 4 2 8 5 7 1 4

输出 2

5

输入 3

2
1 2

输出 3

2

输入 4

6
2 2 3 3 5 5

输出 4

6