Minimum Operations to Palindrome

You are given an array of integers. In one operation, you can merge two adjacent elements by replacing them with their sum. The goal is to transform the array into a palindrome (an array that reads the same forward and backward) using the minimum number of operations.

Formally, let \(A[0 \dots n-1]\) be the input array. In one step, if you choose two adjacent indices \(i\) and \(i+1\), you replace them with a single element \(A[i] + A[i+1]\). Continue performing such operations until the array is a palindrome. Output the minimum number of operations required.

Note: A palindrome satisfies \(A[i] = A[n-1-i]\) for all \(0 \leq i < n\).

inputFormat

The first line contains an integer n (\(1 \le n \le 10^5\)), the number of elements in the array. The second line contains n space-separated integers, representing the elements of the array.

outputFormat

Output a single integer, the minimum number of operations required to convert the given array into a palindrome.

## sample

5
1 4 5 9 1

1

</p>