CF1154E Two Teams

有 $n$ 个学生站成一排。两位教练要组建两支队伍——第一位教练选择第一支队伍，第二位教练选择第二支队伍。 第 $i$ 个学生拥有整数编程能力 $a_i$。所有学生的编程能力互不相同，且都在 $1$ 到 $n$ 之间（包含 $1$ 和 $n$）。 首先，第一位教练会在所有尚未被选入任何队伍的学生中，选择编程能力最大的学生，并将他左右两侧最近的 $k$ 个学生一同选入（如果左侧或右侧不足 $k$ 个学生，则将所有剩余的学生一同选入）。所有被选中的学生离开队伍，加入第一支队伍。接着，第二位教练以相同的方式选择学生（但被他选中的学生加入第二支队伍）。然后再轮到第一位教练，如此反复，直到所有学生都被分配到某支队伍为止（即队伍为空时过程结束）。 你的任务是确定每位学生最终会加入第一支队伍还是第二支队伍。

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 2 \cdot 10^5$），分别表示学生人数和每次操作中左右可选学生的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），其中 $a_i$ 表示第 $i$ 个学生的编程能力。保证所有编程能力互不相同。

输出一个长度为 $n$ 的字符串，第 $i$ 个字符为 $1$ 表示第 $i$ 个学生加入第一支队伍，否则为 $2$。

在第一个样例中，第一位教练选择了第 $3$ 位学生，队伍变为空（所有学生都加入了第一支队伍）。 在第二个样例中，第一位教练选择了第 $4$ 位学生，队伍变为 $[2, 1]$（编程能力为 $[3, 4, 5]$ 的学生加入了第一支队伍）。然后第二位教练选择了第 $1$ 位学生，队伍变为空（编程能力为 $[1, 2]$ 的学生加入了第二支队伍）。 在第三个样例中，第一位教练选择了第 $1$ 位学生，队伍变为 $[1, 3, 5, 4, 6]$（编程能力为 $[2, 7]$ 的学生加入了第一支队伍）。然后第二位教练选择了第 $5$ 位学生，队伍变为 $[1, 3, 5]$（编程能力为 $[4, 6]$ 的学生加入了第二支队伍）。接着第一位教练选择了第 $3$ 位学生，队伍变为 $[1]$（编程能力为 $[3, 5]$ 的学生加入了第一支队伍）。最后第二位教练选择了剩下的学生（编程能力为 $1$ 的学生加入了第二支队伍）。 在第四个样例中，第一位教练选择了第 $3$ 位学生，队伍变为 $[2, 1]$（编程能力为 $[3, 4, 5]$ 的学生加入了第一支队伍）。然后第二位教练选择了第 $1$ 位学生，队伍变为空（编程能力为 $[1, 2]$ 的学生加入了第二支队伍）。 由 ChatGPT 4.1 翻译