[R73B]爱吃白饭的大肥鱼2 - 代码源竞赛平台

时空限制

1S/256M

爱吃白饭的大肥鱼游入了一条狭长的水道中。这条水道被划分为 $m$ 个连续的水域位置，从左到右依次编号为 $1, 2, \ldots, m$ 。

大肥鱼的身躯庞大，会占据水道中一段连续的位置。初始时，大肥鱼还处于未膨胀状态，只占据编号为 $s$ 的水域位置（即初始覆盖区间为 $[s,s]$ ）。

接下来，有 $n$ 条活泼的小鱼依次游入水道，第 $i$ 条小鱼会突然出现在编号为 $x_i$ 的水域位置。由于大肥鱼十分慵懒，它对于第 $i$ 条小鱼的处理方式如下（设当前大肥鱼身体覆盖的水域区间为 $[l,r]$ ）：

如果 $l \le x_i \le r$ ： 这条小鱼自投罗网，直接出现在了大肥鱼的嘴边并被一口吃掉，计为一次成功捕食。大肥鱼吃饱后身体会长大变胖，在不超出水道边界的前提下，其覆盖区间向左右各扩张一个位置，即变为 $[\max(1, l-1), \min(m, r+1)]$ ；
如果 $x_i < l$ ： 小鱼出现在大肥鱼的左侧，大肥鱼够不着，没有吃到。但贪吃的大肥鱼为了下一顿，会艰难地将笨重的身体整体向左挪动一个位置，即覆盖区间变为 $[l-1, r-1]$ ；
如果 $x_i > r$ ： 小鱼出现在大肥鱼的右侧，大肥鱼同样没有吃到。大肥鱼会将身体整体向右挪动一个位置，即覆盖区间变为 $[l+1, r+1]$ 。

每条小鱼只在出现时被处理一次。没有被吃到的小鱼随后会离开水道，不会再对之后的过程产生影响。

求 $n$ 条小鱼全部出现完毕后，大肥鱼成功吃掉的小鱼总数量，以及大肥鱼最终身体覆盖的水域区间的左右端点位置。

第一行包含三个正整数 $n,m,s$ ，分别表示小鱼的数量、水道包含的水域位置数量，以及大肥鱼初始所在的位置。

第二行包含 $n$ 个正整数 $x_1,x_2,\ldots,x_n$ ，其中 $x_i$ 表示第 $i$ 条小鱼出现的位置。

输出一行三个整数，依次表示大肥鱼成功吃掉的小鱼总数量，以及最终身体覆盖区间的左右端点。

6 7 4
2 3 4 7 6 1

4 1 7

大肥鱼覆盖的区间依次变为 $[3,3]$ 、 $[2,4]$ 、 $[1,5]$ 、 $[2,6]$ 、 $[1,7]$ 、 $[1,7]$ ，共吃掉 $4$ 条小鱼。

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 $100\%$ 的数据，满足 $1\le n\le2\times10^5$ ， $1\le m\le10^9$ ， $1\le s,x_i\le m$ 。