Overview

During the process of distributing stickers, we need to determine whether there exists a student who has more stickers than Takahashi only at the moment immediately after student number 2 (Takahashi) receives a sticker, and count the number of such occurrences.

Analysis

Takahashi feels dissatisfied only “immediately after a sticker is given to Takahashi (student 2)”. Therefore, at each such moment, we need to check the following:

• Let \(c_2\) be Takahashi’s current number of stickers
• Let \(max\_other\) be the maximum number of stickers among all students other than Takahashi
• If \(max\_other > c_2\), then add \(1\) to the dissatisfaction count at that timing

The key insight here is that what we need for the check is not “the detailed count for every student” but only “Takahashi’s count” and “the maximum count among other students”.

Why the naive approach is too slow

Every time Takahashi receives a sticker, if we: - Check all students to see if anyone has more stickers than Takahashi,
each check costs \(O(N)\).

In the worst case, Takahashi is called \(O(M)\) times, so the total becomes \(O(NM)\), which is far too slow for \(N, M \le 3\times 10^5\).

How to solve it

Since each student’s count only increases by 1 each time they receive a sticker, we can incrementally update: - Takahashi’s count \(c_2\) - “The maximum count among students other than Takahashi” \(max\_other\)

This way, each check can be done in \(O(1)\).

Simple example

For instance, suppose at some point: - Takahashi’s count is \(c_2 = 2\) - Someone else has 3 stickers, so \(max\_other = 3\)

Even if Takahashi receives the next sticker and \(c_2\) becomes \(3\), the check yields: - \(max\_other(=3) > c_2(=3)\) is false
so no dissatisfaction is added.

Conversely, if \(max\_other = 4\) remained unchanged: - \(4 > 3\) is true, so dissatisfaction increases by 1.

Algorithm

1. Prepare an array cnt, where cnt[x] represents the current number of stickers for student \(x\).
2. Maintain a variable max_other as “the maximum sticker count among students other than Takahashi (student 2)”.
3. Iterate through the distribution order \(P_1, P_2, \dots, P_M\):
   • If x == 2 (Takahashi):
     1. cnt[2] += 1
     2. If max_other > cnt[2], then ans += 1
   • Otherwise (other students):
     1. cnt[x] += 1
     2. If cnt[x] > max_other, update max_other = cnt[x]
4. Output ans.

Since max_other only increases when another student’s count increases, it is always maintained correctly.

Complexity

• Time complexity: \(O(M)\) (processing each distribution once, with \(O(1)\) per step)
• Space complexity: \(O(N)\) (storing each student’s sticker count)

Implementation Notes

• max_other must contain only the maximum count among students other than Takahashi (mixing in Takahashi’s count would break the check).

• The check should be performed only immediately after Takahashi receives a sticker (dissatisfaction does not increase at any other timing).

• Since the input can be large, in Python, fast input methods such as sys.stdin.buffer.read() are effective.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, M = data[0], data[1]
    P = data[2:]

    cnt = [0] * (N + 1)
    max_other = 0
    ans = 0

    for x in P:
        if x == 2:
            cnt[2] += 1
            if max_other > cnt[2]:
                ans += 1
        else:
            cnt[x] += 1
            if cnt[x] > max_other:
                max_other = cnt[x]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.