B - 不満を感じる回数 解説 /

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

配点 : 300 点

問題文

高橋君のクラスには N 人の生徒がいます。生徒にはそれぞれ 1 から N までの出席番号が割り振られています。高橋君の出席番号は 2 です。

ある日、先生はご褒美のシールを M 枚用意し、生徒たちに配ることにしました。最初、どの生徒もシールを 1 枚も持っていません。先生は M 枚のシールを 1 枚ずつ順番に配ります。配る順番は長さ M の数列 P_1, P_2, \dots, P_M で表され、i 枚目のシールは出席番号 P_i の生徒に渡されます。同じ生徒に複数回シールが渡されることもあります。

高橋君は負けず嫌いです。P_i = 2 のとき、すなわち i 枚目のシールが高橋君に渡されたとき、高橋君がそのシールを受け取った直後の時点で、高橋君以外の生徒の中に高橋君よりも厳密に多い枚数のシールを持っている生徒が 1 人でもいれば、高橋君は不満を 1 回感じます。高橋君と同数のシールを持っている生徒がいるだけでは不満を感じません。P_i \neq 2 のとき、すなわち高橋君以外の生徒にシールが渡されたときには、高橋君は不満を感じません。

なお、数列 P に 2 が含まれない（高橋君にシールが一度も渡されない）場合もあり得ます。この場合、高橋君が不満を感じる機会は一度もないため、答えは 0 です。

シールを M 枚すべて配り終えるまでに、高橋君が不満を感じる回数の合計を求めてください。

制約

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

入力

N M
P_1 P_2 \dots P_M
  • 1 行目には、生徒の人数を表す整数 N と、シールの枚数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、シールを配る順番を表す数列 P_1, P_2, \dots, P_M が、スペース区切りで与えられる。
  • P_i は i 枚目のシールを渡す生徒の出席番号であり、1 以上 N 以下の整数である。

出力

高橋君が不満を感じる回数の合計を 1 行で出力せよ。

入力例 1

3 6
1 1 2 1 2 2

出力例 1

2

入力例 2

5 10
1 3 3 2 1 3 2 4 2 5

出力例 2

2

入力例 3

5 12
1 3 4 1 3 2 1 2 5 5 2 2

出力例 3

2

Score : 300 pts

Problem Statement

There are N students in Takahashi's class. Each student is assigned a student number from 1 to N. Takahashi's student number is 2.

One day, the teacher prepared M stickers to distribute to the students. Initially, no student has any stickers. The teacher distributes the M stickers one at a time in order. The distribution order is represented by a sequence of length M: P_1, P_2, \dots, P_M, where the i-th sticker is given to the student with student number P_i. The same student may receive stickers multiple times.

Takahashi is competitive. When P_i = 2, that is, when the i-th sticker is given to Takahashi, if immediately after Takahashi receives that sticker there exists at least one student other than Takahashi who has strictly more stickers than Takahashi, then Takahashi feels frustrated once. He does not feel frustrated merely because some student has the same number of stickers as him. When P_i \neq 2, that is, when a sticker is given to a student other than Takahashi, Takahashi does not feel frustrated.

Note that it is possible that 2 does not appear in the sequence P (Takahashi never receives a sticker). In this case, Takahashi never has an opportunity to feel frustrated, so the answer is 0.

Find the total number of times Takahashi feels frustrated by the time all M stickers have been distributed.

Constraints

  • 2 \leq N \leq 3 \times 10^5
  • 1 \leq M \leq 3 \times 10^5
  • 1 \leq P_i \leq N (1 \leq i \leq M)
  • All inputs are integers.

Input

N M
P_1 P_2 \dots P_M
  • The first line contains an integer N representing the number of students and an integer M representing the number of stickers, separated by a space.
  • The second line contains the sequence P_1, P_2, \dots, P_M representing the order of sticker distribution, separated by spaces.
  • P_i is the student number of the student who receives the i-th sticker, and is an integer between 1 and N, inclusive.

Output

Print the total number of times Takahashi feels frustrated, in a single line.

Sample Input 1

3 6
1 1 2 1 2 2

Sample Output 1

2

Sample Input 2

5 10
1 3 3 2 1 3 2 4 2 5

Sample Output 2

2

Sample Input 3

5 12
1 3 4 1 3 2 1 2 5 5 2 2

Sample Output 3

2