C - Σ Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) および正整数 K が与えられます。

1 以上 K 以下の整数のうち、A の中に一度も現れないものの総和を求めてください。

制約

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

入力

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

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4 5
1 6 3 1

出力例 1

11

1 以上 5 以下の整数のうち、A の中に一度も現れないものは 2,4,5 の 3 つです。

よって、それらの総和である 2+4+5=11 を出力します。

入力例 2

1 3
346

出力例 2

6

入力例 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

出力例 3

12523196466007058

Score: 250 points

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.

Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.

Constraints

  • 1\leq N \leq 2\times 10^5
  • 1\leq K \leq 2\times 10^9
  • 1\leq A_i \leq 2\times 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 5
1 6 3 1

Sample Output 1

11

Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.

Thus, print their sum: 2+4+5=11.

Sample Input 2

1 3
346

Sample Output 2

6

Sample Input 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

Sample Output 3

12523196466007058