题目描述

现在给你一个长度为$n$的数组。接下来将它复制总共$n$遍拼接在一起。

例如对于数组$[3, 2, 1]$，复制$3$遍并拼接后是$[3, 2, 1, 3, 2, 1, 3, 2, 1]$。

你的任务是计算复制拼接后的数组中，最长严格上升子序列的长度。例如上面这个例子中，最长可以选出的长度是3。下面展示了选择方案，其中被选择的数字打上了小括号。

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

注1：严格上升即序列中后面的元素严格大于前面的元素。

注2：子序列指原数组中一段不连续的序列。

输入格式

第一行一个正整数$n$，表示数组的长度。

第二行$n$个正整数，按顺序依次表示数组里的数字。

输出格式

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

3
3 2 1

3

5
1 5 1 3 2

4

数据规模与约定

对于$50\%$的数据，$1 \le n \le 50$。

对于$100\%$的数据，$1 \le n \le 50000$, 保证数组中的数字满足$1 \le number \le n$。