Sau khi leo rank Thách đấu thành công trong LTOJ, TuanAnh đã 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, TuanAnh 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 ai TuanAnh 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, TuanAnh 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 TuanAnh 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

• Dòng \(1\): Chứa \(1\) số nguyên dương \(N\) \((1 \leq N \leq 10^5)\) là số lượng quả cầu tuyết.
• Dòng thứ hai chứa N số nguyên \(a_i (1≤ a_i ≤ 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

ABNL có thể gộp quả cầu tuyết có kích thước 6 và 4 lại với nhau, tạo thành dãy đối xứng  [3,10,10,3] với chỉ 1 lần gộp.

3
2 1 4

2

ABNL cần gộp 2 và 1 lại với nhau, sau đó gộp phần này với 4, tạo thành dãy đối xứng [7]. Tổng cộng cần 2 lần gộp.