Array Shrinking

Description:

Input:

The first line contains the single integer $$$n$$$ ($$$1 \le n \le 500$$$) — the initial length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 1000$$$) — the initial array $$$a$$$.

Output:

Print the only integer — the minimum possible length you can get after performing the operation described above any number of times.

Sample Input:

5
4 3 2 2 3

Sample Output:

2

Sample Input:

7
3 3 4 4 4 3 3

Sample Output:

2

Sample Input:

3
1 3 5

Sample Output:

3

Sample Input:

1
1000

Sample Output:

1

Note:

In the first test, this is one of the optimal sequences of operations: $$$4$$$ $$$3$$$ $$$2$$$ $$$2$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$\rightarrow$$$ $$$5$$$ $$$3$$$.

In the second test, this is one of the optimal sequences of operations: $$$3$$$ $$$3$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$3$$$ $$$3$$$ $$$\rightarrow$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$4$$$ $$$4$$$ $$$4$$$ $$$\rightarrow$$$ $$$5$$$ $$$5$$$ $$$4$$$ $$$\rightarrow$$$ $$$6$$$ $$$4$$$.

In the third and fourth tests, you can't perform the operation at all.