Colored Balls in a Tube

A tube contains n balls of various colors arranged in a line. The balls have the same diameter and the colors from one end to the other are given by \(c_1, c_2, \ldots, c_n\). Little E has an empty cup whose opening is only slightly larger than the ball’s diameter. Hence, he can only place one ball at a time into the cup and the balls can only be stacked vertically.

There is one more twist: whenever two adjacent balls in the cup have the same color, they vanish immediately. Due to the structure of the tube, at each step Little E can only remove the outermost ball at one end of the tube (i.e. he may choose the leftmost ball or the rightmost ball currently in the tube) and immediately deposit it into the cup.

Your task is to determine, after all the balls have been removed from the tube, the minimum possible number of balls remaining in the cup. Under the assumption that this minimum is achieved, determine also the minimum cup capacity required – that is, the smallest maximum number of balls that appear in the cup during the process.

The ball‐elimination process can be understood as a stack operation. When a new ball is added: if the cup is non–empty and the ball being added has the same color as the ball on the top of the cup, then the top ball is removed instead of adding the new ball (i.e. both vanish). Otherwise, the new ball is pushed onto the stack. Note that the order in which balls are extracted from the tube (by choosing one of its two ends at every step) affects the final outcome.

Input Note: Colors will be represented by integers.

inputFormat

The first line contains an integer \(n\) (the number of balls). The second line contains \(n\) integers \(c_1, c_2, \ldots, c_n\) representing the colors of the balls in order.

outputFormat

Output two integers separated by a space: the minimum number of balls remaining in the cup after the process, and the minimum cup capacity required (i.e. the maximum number of balls in the cup at any moment during an optimal process).

sample

2
1 1

0 1