There are $n$ colored balls stuck in a pipe. The balls all have the same diameter. Their colors from one end to the other are $c_1, c_2, \dots, c_n$.
Little E has an empty cup. The diameter of the cup's opening is just slightly larger than the diameter of the balls, so Little E can place balls into the cup, but only one at a time, and the balls must be stacked vertically. Two adjacent balls of the same color in the cup will disappear together.
Due to the nature of the pipe, Little E can only choose one end of the pipe at a time, take out the outermost ball, and immediately place it into the cup.
Determine the minimum number of balls remaining in the cup after all balls have been removed from the pipe, and the minimum cup capacity required to achieve this.
Input
The first line contains a positive integer $n$.
The second line contains $n$ positive integers, where the $i$-th integer represents $c_i$.
Output
Output a single line containing two non-negative integers. The first number is the minimum number of balls remaining in the cup. The second number is the minimum capacity the cup must have to achieve this minimum.
Examples
Input 1
12
3 5 1 4 9 3 3 5 1 4 9 3Output 1
0 5Note 1
One optimal strategy is as follows:
First, place the $3$s from both ends into the cup to eliminate them.
3.png
Then, place $5, 1, 4, 9$ from the left end into the cup one by one; at this point, there are $4$ balls in the cup.
4.png
Next, place $9, 4$ from the right end into the cup one by one. Each time a ball is placed, it will be eliminated with another ball in the cup. After placing $9$ and before elimination, the cup contains $5, 1, 4, 9, 9$, so the cup must be able to hold $5$ balls.
5.png
Then, place $3, 3$ from the left end into the cup; at this point, there are $2$ balls in the cup.
7.png
Finally, place $1, 5$ from the right end into the cup one by one. At this point, the cup is empty.
9.png
Alternatively, see Sampledescription.pptx in the provided files.
Subtasks
It is guaranteed that $n \le 50$ and $1 \le c_i \le n$.