E - Organizing Books Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は図書館の司書です。図書館には N 個の棚が一列に並んでおり、左から順に 1, 2, \ldots, N と番号が付けられています。

ある日、M 冊の本を棚に戻す作業を行います。本を戻す順番は決まっており、1 番目、2 番目、\ldots、M 番目の順に一冊ずつ棚に戻します。i 番目 (1 \leq i \leq M) に戻す本の、戻すべき棚の番号は G_i です。なお、同じ棚に複数の本が戻されることもあります。

高橋君は i 番目 (1 \leq i \leq M) の本を棚に戻すたびに、以下のように定義される値 L_i を記録します。

  • L_i：i+1 番目、i+2 番目、\ldots、M 番目に戻す予定の M - i 冊の本（すなわち、i 番目の本を戻した時点でまだ棚に戻していない本すべて）のうち、戻すべき棚の番号が G_i 未満であるものの冊数。i = M のとき、該当する本は 0 冊であるため L_M = 0 です。

高橋君は一日の作業終了後、記録した値の合計 L_1 + L_2 + \cdots + L_M を報告書に書かなければなりません。

棚の数 N、本の数 M、および各本を戻すべき棚の番号 G_i が与えられるとき、L_1 + L_2 + \cdots + L_M の値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq G_i \leq N (1 \leq i \leq M)
  • 入力はすべて整数である

入力

N M
G_1
G_2
\vdots
G_M
  • 1 行目には、棚の数を表す整数 N と本の数を表す整数 M が、スペース区切りで与えられる。
  • 続く M 行のうち i 行目 (1 \leq i \leq M) には、i 番目に戻す本の、戻すべき棚の番号 G_i が与えられる。

出力

L_1 + L_2 + \cdots + L_M の値を 1 行で出力せよ。

入力例 1

5 4
3
1
4
2

出力例 1

3

入力例 2

3 5
2
3
1
2
1

出力例 2

6

入力例 3

10 8
5
3
8
1
7
2
6
4

出力例 3

15

入力例 4

100 12
10
9
8
7
6
5
4
3
2
1
1
1

出力例 4

63

入力例 5

1 1
1

出力例 5

0

Score : 466 pts

Problem Statement

Takahashi is a librarian at a library. The library has N shelves arranged in a row, numbered 1, 2, \ldots, N from left to right.

One day, he performs the task of returning M books to the shelves. The order of returning books is fixed: he returns them one by one in order — the 1st book, the 2nd book, \ldots, the Mth book. The shelf number to which the i-th (1 \leq i \leq M) book should be returned is G_i. Note that multiple books may be returned to the same shelf.

Each time Takahashi returns the i-th (1 \leq i \leq M) book to its shelf, he records a value L_i defined as follows:

  • L_i: Among the M - i books scheduled to be returned as the (i+1)-th, (i+2)-th, \ldots, M-th books (that is, all books that have not yet been returned to the shelves at the moment the i-th book is returned), the number of books whose destination shelf number is less than G_i. When i = M, there are 0 such books, so L_M = 0.

After the day's work is finished, Takahashi must write the total of the recorded values L_1 + L_2 + \cdots + L_M in his report.

Given the number of shelves N, the number of books M, and the destination shelf number G_i for each book, find the value of L_1 + L_2 + \cdots + L_M.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq G_i \leq N (1 \leq i \leq M)
  • All input values are integers

Input

N M
G_1
G_2
\vdots
G_M
  • The first line contains an integer N representing the number of shelves and an integer M representing the number of books, separated by a space.
  • The i-th (1 \leq i \leq M) of the following M lines contains G_i, the destination shelf number for the i-th book to be returned.

Output

Output the value of L_1 + L_2 + \cdots + L_M on a single line.

Sample Input 1

5 4
3
1
4
2

Sample Output 1

3

Sample Input 2

3 5
2
3
1
2
1

Sample Output 2

6

Sample Input 3

10 8
5
3
8
1
7
2
6
4

Sample Output 3

15

Sample Input 4

100 12
10
9
8
7
6
5
4
3
2
1
1
1

Sample Output 4

63

Sample Input 5

1 1
1

Sample Output 5

0