Alaric Journey
本题没有可用的提交语言。
Description
In an ancient realm, a talented alchemist named Alaric was on a quest to unlock the secrets of immortality. Over time, Alaric stumbled upon an enigma that even challenged his supernatural abilities.
Alaric discovered an ancient parchment describing a set of magical numbers that were pivotal in creating the elixir of immortality. These numbers were arranged in an array, and to unleash the power of the potion, the array had to become a "magic palindrome."
An array is a "magic palindrome" if it is symmetric and reads the same from left to right and from top to bottom. To transform an array into a magic palindrome, Alaric could perform the following operation: take two adjacent numbers in the array and replace them with their sum.
Help Alaric find the minimum number of operations he needs to perform to turn the array of numbers into a "magic palindrome" and unlock the power of the elixir of immortality.
The first line contains an integer $N$ $(1 \leq N \leq 10^6)$, the number of elements in the array. The second line contains $N$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_N$ $(1 \leq a_i \leq 10^6)$, representing the elements of the array.
An integer, representing the minimum number of operations required to transform the array into a palindrome.
Input
The first line contains an integer $N$ $(1 \leq N \leq 10^6)$, the number of elements in the array. The second line contains $N$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_N$ $(1 \leq a_i \leq 10^6)$, representing the elements of the array.
Output
An integer, representing the minimum number of operations required to transform the array into a palindrome.
5
1 2 3 5 1
3
1 10 100
2
2 2
1
2
0
Note
An array is a palindrome if it remains the same when its elements are viewed in reverse order. For example:
[1, 2, 1] is a palindrome.
[100] is a palindrome.
[13, 41, 14, 31] is not a palindrome.