K - 加算と減算 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 5 点

問題文

長さ N の整数列 A = (A_1, A_2, \dots, A_N) があります。
また、あなたは整数 x を持っています。はじめ x=0 です。 あなたは次の N 回の操作を行います。

  • i = 1, 2, \dots, N の順に、次の 3 種類の操作のうちどれか 1 つを行う。
    • x を x + A_i に置き換える。
    • x を \vert x - A_i \vert に置き換える。
    • 何もしない。

N 回の操作が終了した時点での x の値としてあり得るものの個数を求めてください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 2 \times 10^6
  • \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 2 \times 10^6
  • 入力される値は全て整数

部分点

この問題には部分点が設定されている。

  • \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 5 \times 10^5 であるデータセットに正解した場合、4 点が与えられる。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

N 回の操作が終了した時点での x の値としてあり得るものの個数を出力せよ。

入力例 1

3
2 7 5

出力例 1

10

例えば次の操作を行うことで操作後の x を 9 にすることができます。

  • はじめ、x=0 である。
  • i=1 の時、x を \vert x-A_i \vert = \vert 0-2 \vert = 2 に置き換える。
  • i=2 の時、x を x+A_i=2+7=9 に置き換える。
  • i=3 の時、何もしない。

入力例 2

10
49 85 36 30 71 65 38 45 73 27

出力例 2

454

Score : 5 points

Problem Statement

You are given an integer sequence A = (A_1, A_2, \dots, A_N) of length N.
You also have an integer x, which is initially 0.

You will perform the following N operations:

  • For i = 1, 2, \dots, N, choose exactly one of the following three operations:
    • Replace x with x + A_i.
    • Replace x with \vert x - A_i \vert.
    • Do nothing.

Find the number of possible values of x after all N operations are completed.

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 2 \times 10^6
  • \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 2 \times 10^6
  • All input values are integers

Partial Score

This problem has partial scoring.

  • If you solve the dataset with \displaystyle 1 \leq \sum_{i=1}^N A_i \leq 5 \times 10^5, you will get 4 points.

Input

The input is given from standard input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the number of possible values of x after all N operations are completed.

Sample Input 1

3
2 7 5

Sample Output 1

10

For example, you can obtain x = 9 by performing the following operations:

  • Initially, x = 0.
  • At i = 1, replace x with \vert x - A_i \vert = \vert 0 - 2 \vert = 2.
  • At i = 2, replace x with x + A_i = 2 + 7 = 9.
  • At i = 3, do nothing.

Sample Input 2

10
49 85 36 30 71 65 38 45 73 27

Sample Output 2

454