#G1130. [GESP202509 四级] 最长连续段

[GESP202509 四级] 最长连续段

[GESP202509 四级] 最长连续段

题目描述

对于 kk 个整数构成的数组 b1,b2,…,bkb_1,b_2,\ldots,b_k,如果对 1≤i<k1 \le i < k 都有 bi+1=bi+1b_{i+1}=b_i+1,那么称数组 bb 是一个连续段。

给定由 nn 个整数构成的数组 a1,a2,…,ana_1,a_2,\ldots,a_n,你可以任意重排数组 aa 中元素顺序。请问在重排顺序之后,aa 所有是连续段的子数组中,最长的子数组长度是多少?

例如,对于数组 [1,0,2,4][1,0,2,4],可以将其重排为 [4,0,1,2][4,0,1,2],有以下 1010 个子数组:

$$[4], [0], [1], [2], [4,0], [0,1], [1,2], [4,0,1], [0,1,2], [4,0,1,2]$$

其中除 [4,0][4,0]、[4,0,1][4,0,1]、[4,0,1,2][4,0,1,2] 以外的子数组均是连续段,因此是连续段的子数组中,最长子数组长度为 33。

输入格式

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

第二行,nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示数组中的整数。

输出格式

一行,一个整数,表示数组 aa 重排顺序后,所有是连续段的子数组的最长长度。

样例 #1

样例输入 #1

4
1 0 2 4

样例输出 #1

3

样例 #2

样例输入 #2

9
9 9 8 2 4 4 3 5 3

样例输出 #2

4

数据范围

测试点占比 nn 范围 其他
40%40\% 1≤n≤81 \le n \le 8 —
所有测试点 1≤n≤1051 \le n \le 10^5 −109≤ai≤109-10^9 \le a_i \le 10^9