CF1288E Messenger Simulator

Polycarp 是一位非常活跃的流行聊天软件用户，他一直在和朋友们聊天。他有 $n$ 个朋友，编号从 $1$ 到 $n$。 我们称长度为 $n$ 的排列为一个数组，该数组包含 $1$ 到 $n$ 的每个整数且每个只出现一次。 因此，他最近的聊天列表可以用一个长度为 $n$ 的排列 $p$ 表示。$p_1$ 表示 Polycarp 最近一次聊天的朋友，$p_2$ 表示第二最近，以此类推。 最开始，Polycarp 的最近聊天列表 $p$ 是 $1, 2, \dots, n$（也就是说，是一个单位排列）。 之后，他收到了 $m$ 条消息，第 $j$ 条消息来自朋友 $a_j$。这会导致朋友 $a_j$ 移动到排列的第一位，原本在第一位到 $a_j$ 当前所在位置之间的所有人向后移动一位。注意，如果 $a_j$ 已经在第一位，则什么都不会发生。 例如，假设当前的聊天列表为 $p = [4, 1, 5, 3, 2]$： - 如果收到朋友 $3$ 的消息，则 $p$ 变为 $[3, 4, 1, 5, 2]$； - 如果收到朋友 $4$ 的消息，则 $p$ 不变，仍为 $[4, 1, 5, 3, 2]$； - 如果收到朋友 $2$ 的消息，则 $p$ 变为 $[2, 4, 1, 5, 3]$。 对于每个朋友，考虑他在初始状态以及每次收到消息后所处的所有位置。Polycarp 想知道，每个朋友曾经处于的最小位置和最大位置分别是多少。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 3 \cdot 10^5$），分别表示 Polycarp 的朋友数和收到的消息数。 第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$（$1 \le a_i \le n$），表示每条消息来自的朋友编号。

输出 $n$ 对整数。对于每个朋友，输出他在初始状态及每次收到消息后所处的最小位置和最大位置。

在第一个样例中，Polycarp 的最近聊天列表变化如下： - $[1, 2, 3, 4, 5]$ - $[3, 1, 2, 4, 5]$ - $[5, 3, 1, 2, 4]$ - $[1, 5, 3, 2, 4]$ - $[4, 1, 5, 3, 2]$ 例如，朋友 $2$ 的位置依次为 $2, 3, 4, 4, 5$，其中最小值为 $2$，最大值为 $5$。因此，朋友 $2$ 的答案为一对 $(2, 5)$。 在第二个样例中，Polycarp 的最近聊天列表变化如下： - $[1, 2, 3, 4]$ - $[1, 2, 3, 4]$ - $[2, 1, 3, 4]$ - $[4, 2, 1, 3]$ 由 ChatGPT 4.1 翻译