Sau khi leo rank Thách đấu thành công trong LQDOJ Arena, ABNL đã quyết định dành một đêm Giáng Sinh thật đặc biệt. Anh rủ AKA và trưởng thôn Minh đi dạo phố để tận hưởng không khí Noel.

AKA là một người rất yêu thích mọi thứ đối xứng, giống như cái tên của anh ấy. Trưởng thôn Minh cũng rất thích đối xứng, bởi vì Minh thích mọi điều bắt đầu bằng chữ M, chẳng hạn như Man Utd, Mordekaiser, Manbo, và đặc biệt chữ cái M cũng mang tính đối xứng. Để tặng món quà trước khi qua Úc, ABNL quyết định tạo ra một món quà đặc biệt mang tính đối xứng từ những quả cầu tuyết trên phố.

Dọc theo con đường, có rất nhiều quả cầu tuyết với kích thước \(a_i\). ABNL muốn gom chúng lại để tạo thành một dãy đối xứng hoàn hảo. Trong một lần gộp, ABNL có thể chọn hai quả cầu tuyết liền kề và gộp chúng lại thành một quả cầu mới, với kích thước bằng tổng kích thước của hai quả cầu ban đầu.

Vì số quả cầu quá nhiều, hãy giúp ABNL tính số lần gộp tối thiểu cần thiết để biến dãy ban đầu thành một dãy đối xứng.

Input

• Một dòng chứa một số nguyên dương \(N\) \((1 \leq N \leq 10^3)\) là số lượng quả cầu tuyết.
• Dòng thứ hai chứa \(N\) số nguyên \(a_i\) \((1 \leq a_i \leq 10^6)\), là kích thước của các quả cầu tuyết.

Output

• In ra một số nguyên duy nhất là số lần gộp tối thiểu cần thực hiện để biến dãy cầu tuyết thành một dãy đối xứng.

Example

5
3 10 6 4 3

1

3
2 1 4

2