#P1140. 复制

复制

题目描述

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

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

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

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

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

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

输入格式

第一行一个正整数nn,表示数组的长度。

第二行nn个正整数,按顺序依次表示数组里的数字。

输出格式

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

3
3 2 1
3
5
1 5 1 3 2
4

数据规模与约定

对于50%50\%的数据,1n501 \le n \le 50

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