N - 40B of calculations Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

長さ N の整数列 A が与えられます。
高橋君は、 N \times N のマス目の上から i 番目、左から j 番目のマスに A_i-A_j の値を書き込みました。
このマス目には何種類の値が書き込まれたでしょうか?

制約

  • 入力は全て整数
  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5

入力

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

N
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

3
5 2 3

出力例 1

7

数が書き込まれた後のマス目の状態は以下の通りで、ここには 7 種類の値が含まれます。

入力例 2

10
13 21 34 55 89 1 2 3 5 8

出力例 2

75

Score : 6 points

Problem Statement

You are given an integer sequence A of length N.
In an N \times N grid, Takahashi has written the value A_i-A_j in the square at the i-th row from the top and j-th column from the left.
How many different values are written in the grid?

Constraints

  • All values in input are integers.
  • 1 \le N \le 2 \times 10^5
  • 1 \le A_i \le 2 \times 10^5

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

3
5 2 3

Sample Output 1

7

After the numbers are written, the grid looks as follows, containing 7 different values.

Sample Input 2

10
13 21 34 55 89 1 2 3 5 8

Sample Output 2

75