Xếp gạch

An rất thích trò chơi xếp gạch. Với những chồng gạch đang xếp dở dang, An suy nghĩ cách điều chỉnh lại các chồng gạch sao cho nó đối xứng. Một dãy $N$ chồng gạch được đánh số từ $1$ đến $N$ và chồng gạch thứ $i$ có chiều cao là $h_i$, được gọi là đối xứng nếu $h_i=h_{N-i+1}$ với $1\le i\le N$.

Tại mỗi bước điều chỉnh, hai chồng gạch liền kề có thể được thay thế bằng một chồng gạch mới có chiều cao là tổng chiều cao của hai chồng gạch đó (chồng mới nằm đúng vị trí của hai chồng cũ). Có thể thấy rằng sau mỗi bước điều chỉnh số lượng chồng gạch giảm đi $1$. Một dãy chỉ gồm một chồng gạch cũng là dãy đối xứng.

Yêu cầu: Hãy viết một chương trình cho biết số bước điều chỉnh tối thiểu cần thực hiện để có được một dãy chồng gạch đối xứng.

Dữ liệu vào

• Dòng đầu là một số nguyên $N$ cho biết số lượng chồng gạch ban đầu.
• Dòng thứ hai chứa $N$ số nguyên $h_1,h_2,\dots ,h_N$ lần lượt là chiều cao các chồng gạch ($1\le h_i\le {10}^9$).

Dữ liệu ra

In ra một số nguyên cho biết số bước điều chỉnh tối thiểu cần thực hiện để có được một dãy chồng gạch đối xứng.

Ràng buộc

• $1\le N\le {10}^6$.
• $1\le h_i\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $1\le N\le 10$.
• Subtask 2 ($30\%$ số điểm): $11\le N\le 1000$.
• Subtask 3 ($40\%$ số điểm): $1001\le N\le {10}^6$.

Ví dụ