102002: [AtCoder]ABC200 C - Ringo's Favorite Numbers 2

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:2 Solved:0

Description

Score : $300$ points

Problem Statement

Ringo loves the integer $200$. Solve the problem below for him.
Given a sequence $A$ of $N$ positive integers, find the pair of integers $(i, j)$ satisfying all of the following conditions:

  • $1 \le i < j \le N$;
  • $A_i - A_j$ is a multiple of $200$.

Constraints

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

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

6
123 223 123 523 200 2000

Sample Output 1

4

For example, for $(i, j) = (1, 3)$, $A_1 - A_3 = 0$ is a multiple of $200$.
We have four pairs satisfying the conditions: $(i,j)=(1,3),(1,4),(3,4),(5,6)$.


Sample Input 2

5
1 2 3 4 5

Sample Output 2

0

There may be no pair satisfying the conditions.


Sample Input 3

8
199 100 200 400 300 500 600 200

Sample Output 3

9

Input

题意翻译

对 $200$ 这个数情有独钟的苹果先生拜托你来解决这个问题。 给定一个长度为 $N$ 的正整数序列 $A$,请求出所有满足 $1 \leq i < j \leq N$ 且 $A_i-A_j$ 为 $200$ 的倍数的二元组 $(i, j)$ 的个数。

加入题单

算法标签: