You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

本学期我们学习了最长上升子序列：最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

给定一个长度为$n$的数列$a_i$，求$a_i$的子序列$b_i$的最长长度，满足$b_i$ 和 $b_{i-1}$不相等($2 \leq i \leq len$)。

即你需要求一个子序列，使得子序列每一项与前一项都是不同的（如果他有前一项的话）

Format

Input

输入共 $2$ 行

第一行包括一个整数 $n$

第二行包括 $n$ 个整数，第 $i$ 个整数表示 $a_i$

Output

输出共一行,包括一个整数，表示子序列 $b_i$ 的最长长度。

Samples

样例输入 1

3
1 2 3

样例输出 1

3

样例输入 2

3
3 2 1

样例输出 2

3

样例输入 3

3
1 1 1

样例输出 3

1

Limitation

对于 $20\%$ 的数据满足 $1 \leq n \leq 10$

对于 $50\%$ 的数据满足 $1 \leq n \leq 1000$

对于 $100\%$ 的数据满足 $1 \leq n \leq 1000000$, $|a_i| \leq 10^9$