#P52083. 「THUPC 2021」小 E 爱消除

「THUPC 2021」小 E 爱消除

题目描述

管道中塞着 nn 个彩色的球。这些球的直径相同。从一端到另一端它们的颜色分别为 c1,c2,,cnc_1,c_2,\cdots,c_n

小E有一个空的杯子。杯口的直径恰好比球的直径大一些,所以小 E 可以把球放入杯子中,但一次只能放入一个,并且球在杯子中只能竖直叠放。杯子中两个相邻的同色球会一起消失。

由于管道的特殊性,小 E 每次只能选择管道的一端,将最靠外的球取出,然后马上放进杯子里。

问当管道中的球全部取出后,杯子里最少会剩下几个球,以及在此前提下至少需要多大的杯子。

输入格式

第一行一个正整数 nn

第二行 nn 个正整数,第 ii 个表示 cic_i

输出格式

输出一行,包含两个非负整数。第一个数表示杯子里剩下球数的最小值。第二个数表示在此前提下杯子需要至少能装下多少个球。

样例

12
3 5 1 4 9 3 3 5 1 4 9 3

0 5

一种最优的方案如下:

先将两端的 33 放入杯子中消去。

3.png

然后把左端的 5,1,4,95,1,4,9 依次放入杯子,这时杯子中有 44 个球。

4.png

再把右端的 9,49,4 依次放入杯子,每放入一个球就会和杯子里的另一个球消去。在放入 99 后消去前杯子中有 5,1,4,9,95,1,4,9,9,所以杯子需要能够容纳 55 个球。

5.png

接着把左端的 3,33,3 放入杯子,这时被杯子中有 22 个球。

7.png

最后把右端的 1,51,5 依次放入杯子。这时杯子是空的。

9.png

或见下发文件中的 [Sampledescription.pptx](file:Sampledescription.pptx)。

子任务

保证 n50n\le 501cin1\le c_i\le n