TopCoder

暴力又被TLE
PY派對

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

Description

小 P 有一個由 $n$ 個正整數組成的序列 $a_1, a_2, \ldots, a_n$,他正在玩一個天平遊戲。

在天平遊戲中,小 P 可以重複進行以下操作:選擇序列中相鄰的兩個數字 $a_i$ 與 $a_{i+1}$,將它們合併成一個數字,合併後的數字為 $a_i + a_{i+1}$。合併之後,整個序列的長度會減少 $1$,合併的數字取代原本那兩個數字的位置。

小 P 覺得,當序列從左往右讀和從右往左讀完全相同時,天平才算是平衡的。請你幫小 P 計算,最少需要進行幾次合併操作,才能讓天平變成平衡的。

Input Format

第一行輸入一個正整數 $n$,代表序列的長度。

第二行輸入 $n$ 個正整數 $a_1, a_2, \ldots, a_n$,以空白分隔,代表序列中的每一個數字。

  • $1 \le n \le 2 \times 10^ 5$
  • $1 \le a_i \le 10^ 9$

Output Format

輸出一個整數,代表最少需要進行的合併操作次數,使天平是平衡的。

Sample Input 1

4
1 2 3 1

Sample Output 1

1

Sample Input 2

4
1 1 1 1

Sample Output 2

0

Sample Input 3

3
4 2 3

Sample Output 3

2

Hints

Problem Source

2026 YTP 國中組初賽 p3

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測試資料 0
2 0~21 無額外限制 15

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 1 2
1 1000 1048576 65536 1 2
2 1000 1048576 65536 1 2
3 1000 1048576 65536 2
4 1000 1048576 65536 2
5 1000 1048576 65536 2
6 1000 1048576 65536 2
7 1000 1048576 65536 2
8 1000 1048576 65536 2
9 1000 1048576 65536 2
10 1000 1048576 65536 2
11 1000 1048576 65536 2
12 1000 1048576 65536 2
13 1000 1048576 65536 2
14 1000 1048576 65536 2
15 1000 1048576 65536 2
16 1000 1048576 65536 2
17 1000 1048576 65536 2
18 1000 1048576 65536 2
19 1000 1048576 65536 2
20 1000 1048576 65536 2
21 1000 1048576 65536 2