Description

There are $n$ colored balls stuffed in a pipe. All balls have the same diameter. From one end to the other, their colors are $c_1,c_2,\ldots,c_n$.

Little E has an empty cup. The diameter of the cup opening is just slightly larger than the diameter of a ball, so Little E can put balls into the cup, but only one at a time, and the balls can only be stacked vertically in the cup. Any two adjacent balls of the same color in the cup will disappear together.

Because of the special structure of the pipe, each time Little E can only choose one end of the pipe, take out the outermost ball, and then immediately put it into the cup.

After all balls in the pipe have been taken out, ask for the minimum number of balls that can remain in the cup, and under this condition, the minimum required cup capacity.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers, where the $i$-th one represents $c_i$.

Output Format

Output one line containing two non-negative integers. The first number is the minimum possible number of balls remaining in the cup. The second number is the minimum number of balls the cup must be able to hold under this condition.

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

0 5

Hint

[Sample Explanation]

One optimal plan is as follows:

First, put the $3$ at both ends into the cup to eliminate them.

Then put the left-end balls $5,1,4,9$ into the cup in order. At this time there are $4$ balls in the cup.

Then put the right-end balls $9,4$ into the cup in order. Each time you put one in, it will eliminate with another ball in the cup. Before the elimination after putting in $9$, the cup contains $5,1,4,9,9$, so the cup needs to be able to hold $5$ balls.

Next put the left-end balls $3,3$ into the cup. At this time there are $2$ balls in the cup.

Finally put the right-end balls $1,5$ into the cup in order. Now the cup is empty.

The picture can be found in the attached file Sampledescription.pptx.

[Constraints]

It is guaranteed that $1 \le n \le 50$, $1 \le c_i \le n$.

[Source]

From the 2021 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2021).

Resources such as the editorial can be found at https://github.com/yylidiw/thupc_1/tree/master.

Translated by ChatGPT 5