11183: 洛谷P11178 - 配对序列
[Creator : ]
Description
一个序列 $s_1,\ldots s_{2k}$ 是配对的，当且仅当：
- 对于任意 $1\le i \le k$，$s_{2i}=s_{2i-1}$。
- 对于任意 $1\le i<k$，$s_{2i}\ne s_{2i+1}$。
注意，配对的序列长度必然为偶数。
例如，$3,3,5,5,2,2$ 是配对的，而 $2,2,2,2,5,5$（$s_2=s_3$ 不满足第二条要求）或者 $1,2,3,3,1,1$（$s_1\ne s_2$ 不满足第一条要求）都不是配对的。
给出一个数列 $a_1,\ldots, a_n$，求所有配对的子序列长度的最大值。
- 对于任意 $1\le i \le k$，$s_{2i}=s_{2i-1}$。
- 对于任意 $1\le i<k$，$s_{2i}\ne s_{2i+1}$。
注意，配对的序列长度必然为偶数。
例如，$3,3,5,5,2,2$ 是配对的，而 $2,2,2,2,5,5$（$s_2=s_3$ 不满足第二条要求）或者 $1,2,3,3,1,1$（$s_1\ne s_2$ 不满足第一条要求）都不是配对的。
给出一个数列 $a_1,\ldots, a_n$，求所有配对的子序列长度的最大值。
Input
输入的第一行有一个正整数 $n$，表示序列的长度。
第二行有 $n$ 个正整数 $a_1,\ldots,a_n$，表示这个序列。
第二行有 $n$ 个正整数 $a_1,\ldots,a_n$，表示这个序列。
Output
输出一行一个自然数，表示最长的配对子序列长度。特别地，如果不存在非空的配对子序列，那么输出 $0$。
Constraints
对于全体数据，保证 $2\le n\le 5\times 10^5$，$1\le a_i\le 5\times 10^5$。
Sample 1 Input
8
1 2 2 2 2 1 2 2
Sample 1 Output
4
取 $1,1,2,2$ 这个子序列即可。
Sample 2 Input
11
1 1 4 1 1 2 1000 2 5 5 4
Sample 2 Output
6
取 $1,1,2,2,5,5$ 这个配对子序列即可。
Sample 3 Input
500
500 455 455 455 455 422 500 188 188 500 455 455 455 486 166 486 271 114 486 486 99 271 166 399 361 486 4 164 480 293 270 293 258 270 4 270 270 404 294 397 457 397 404 294 457 457 457 397 193 482 273 193 482 360 193 273 171 168 193 168 193 147 168 80 475 98 475 23 317 80 475 409 80 23 475 475 80 23 452 289 262 16 374 452 374 16 374 374 374 374 374 373 373 419 152 419 152 208 373 152 152 298 373 152 152 282 222 282 153 109 153 113 153 123 63 282 63 88 339 286 88 115 286 339 115 339 88 88 115 82 82 403 403 403 82 82 82 82 82 18 82 82 403 387 398 398 398 402 402 398 398 398 402 398 451 497 179 305 305 305 497 497 305 327 242 250 250 346 330 161 267 149 346 346 250 250 345 393 207 345 207 393 393 345 438 207 393 207 207 207 413 315 77 413 77 413 165 77 413 165 165 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 456 335 335 131 335 338 92 92 364 53 335 92 338 364 338 92 92 92 338 335 364 53 53 364 335 92 364 364 338 92 335 92 338 92 364 364 53 53 92 53 335 53 92 335 364 335 321 53 92 335 335 335 338 338 92 364 338 364 428 53 92 134 92 53 335 364 92 335 338 335 92 92 335 335 53 53 53 92 335 92 335 53 53 364 53 364 338 338 53 53 53 338 92 338 364 92 364 335 364 364 53 338 364 364 53 335 338 338 338 335 364 92 53 364 53 338 338 53 53 53 335 92 335 338 335 335 335 92 335 338 335 40 92 92 53 335 338 53 335 338 338 335 92 338 92 335 338 53 364 92 92 364 335 335 338 335 364 92 335 53 364 364 335 335 338 364 364 53 338 338 338 364 364 92 92 92 338 364 338 53 92 19 92 335 53 92 338 364 338 364 364 92 53 338 338 335 338 92 364 364
Sample 3 Output
190