Trên sân đấu có $N$ con quái vật đứng thành một hàng. Con quái vật thứ $i$ có lượng máu là $h_i$.

Bạn cần tiêu diệt tất cả các quái vật trên sân. Để tiêu diệt một con quái vật, bạn phải làm cho lượng máu của nó giảm xuống $0$ hoặc thấp hơn.

Để tiêu diệt quái vật, bạn có thể chọn hai số nguyên $l \le r$ và thực hiện một đòn tấn công diện rộng lên các quái vật từ vị trí $l$ đến $r$.

Khi trúng đòn tấn công này, lượng máu của mỗi quái vật trong phạm vi đó sẽ giảm đi $(N - r + l)!$.

Hãy tìm số lần tấn công diện rộng tối thiểu cần thiết để tiêu diệt tất cả các quái vật.

$n!$ là tích của tất cả các số nguyên từ $1$ đến $n$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$. $(1 \le N \le 500)$

Dòng thứ hai chứa $h_1, h_2, \ldots, h_N$ được phân cách bởi dấu cách. $(1 \le h_i \le 5000)$

Dữ liệu ra

Dòng đầu tiên in ra số lần tấn công diện rộng tối thiểu cần thiết để tiêu diệt tất cả quái vật.

Ví dụ

Dữ liệu vào 1

4
1 2 3 4

Dữ liệu ra 1

2

Dữ liệu vào 2

1
5000

Dữ liệu ra 2

5000