hello !

I was trying to solve thisproblem but i m unable to come up with dp states . please provide some hints or thought process to solve this kind of problems.

Shrink The Array

You are given an array of positive integers A[] of length L. If Ai and Ai+1 both are equal replace them by one element with value Ai+1

. Find out the minimum possible length of the array after performing such operation any number of times.

Note:

After each such operation, the length of the array will decrease by one and elements are renumerated accordingly. Input format

The first line contains a single integer L denoting the initial length of the array A. The second line contains L space integers Ai − elements of array A[]

. Output format

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

1<=L<=500

1<=Ai<=1000

Time Limit

2 second Example Input

7 3 3 4 4 4 3 3 Output

2 Sample test case explanation

3 3 4 4 4 3 3 → 4 4 4 4 3 3 → 4 4 4 4 4 → 5 4 4 4 → 5 5 4 → 6 4. Thus the length of the array is 2.