Array Shrinking

You are given an array $a_1, a_2, \dots, a_n$. You can perform the following operation any number of times:

  • Choose a pair of two neighboring equal elements $a_i = a_{i + 1}$ (if there is at least one such pair).
  • Replace them by one element with value $a_i + 1$.

After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array $a$ you can get?

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.

Examples

input

5
4 3 2 2 3

output

2

input

7
3 3 4 4 4 3 3

output

2

input

3
1 3 5

output

3

input

1
1000

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.

Solution:

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=510;
int dp[N][N],f[N],a[N];
int n;
int gao(int l,int r) {
if (dp[l][r]!=-1) return dp[l][r];
if (l==r) {
return dp[l][r]=a[l];
}
dp[l][r]=0;
rep(k,l,r) {
int f1=gao(l,k),f2=gao(k+1,r);
if (f1!=0&&f2!=0&&f1==f2) dp[l][r]=f1+1;
}
return dp[l][r];
}

int main() {
scanf("%d",&n);
rep(i,0,n) scanf("%d",a+i);
memset(dp,-1,sizeof(dp));
f[0]=0;
rep(i,1,n+1) {
f[i]=n+1;
rep(j,0,i) if (gao(j,i-1)!=0) f[i]=min(f[i],f[j]+1);
}
printf("%d\n",f[n]);
}