题目描述

徐老师现在有一个长度为 $n$ 的数组，然后他会将这个数组复制 $n$ 次拼接在一起

比如初始数组是 $[1,3,2,2]$，拼接 $4$ 次后是 $[1,3,2,2,1,3,2,2,1,3,2,2,1,3,2,2]$

现在徐老师想知道，拼接完以后的数组里的 严格最长上升子序列 长度为多少？

P.S.1 子序列指原数组中一段不需要连续的序列，即任意挑选几个数字，保持相对顺序组成的新序列称为子序列

P.S.2 严格上升子序列是指在这个数组中选出一个子序列，这个子序列中的数字依次递增

例如上述例子中可以选出的严格上升子序列有 $[1],[2],[3],[1,2],[2,3],[1,2,3]$

其中最长的严格上升子序列长度为 $3$

输入格式

输入第一行包含一个正整数 $n$，表示数组的长度

输入第二行包含 $n$ 个正整数，依次表示数组内的每个数字

输出格式

一个整数，表示复制拼接后的数组的最长严格上升子序列的长度。

数据范围

对于 $50\%$ 的数据保证，$1 \leq n \leq 50$

对于 $100\%$ 的数据保证，$1 \leq n \leq 50000$

特别的对于所有数据保证， $1 \leq a_i \leq n$

样例输入1

4
1 3 2 2

样例输出1

3

样例解释1

下面用括号表示选择的数字，以下是其中一组长度为 $3$ 的方案

$[(1),3,(2),2,1,(3),2,2,1,3,2,2,1,3,2,2]$