Contest D15 Round 2

Anh John là người thích dán biểu đồ cột. Anh có đủ miếng dán hình chữ nhật với tất cả các size khác nhau.

Công việc của anh là phải dán kín biểu đồ với số lượng miếng dán của mình. Anh không muốn dán thừa hay thiếu, chống lên nhau hoặc dán dư vào khoảng trống, nhưng anh vẫn muốn dán kín với số lượng miếng dán ít nhất
 

Biểu đồ ban đầu                      Biểu đồ sau khi dán kín

Input

-Nhập số n là số cột của dồ thị (1<=n<=1000)
-Gồm n số a[1] , a[2] … a[i] là chiều cao của cột thứ i (0<=a[i]<=10^9)

Output

-Số lượng miếng dán HCN ít nhất để anh hoàn thành công việc

Example

Input: 
6
5 4 3 2 3 2

6
5 4 3 2 3 26
5 4 3 2 3 2
Output:
5