考虑一条长走廊,它可以分为 $$$n$$$ 大小为 $$$1 \times 1$$$ 的方形单元格。这些单元格从左到右编号为 $$$1$$$ 到 $$$n$$$。
这条走廊里有两个人,一个流氓和一个保安。最初,流氓位于第 $$$a$$$ 单元格,警卫位于第 $$$b$$$ 单元格 ($$$a \ne b$$$)。
可能的情况之一。走廊由$$$7$$$牢房组成,流氓在第$$$3$$$牢房,警卫在第$$$6$$$牢房($$$n = 7$$$,$$$a = 3$$$,$$$b = 6$$$)。
流氓口袋里有$$$m$$$鞭炮,第$$$i$$$鞭炮在点燃后$$$s_i$$$秒内爆炸。
每秒发生以下事件(按顺序,完全按照以下顺序):
1. 首先,流氓要么移动到相邻的牢房(从$$$i$$$牢房,他可以移动到$$$(i + 1)$$$牢房或$$$(i - 1)$$$牢房,并且他不能离开走廊),要么留在他当前所在的牢房。如果流氓不动,他可以点燃一根鞭炮并将其扔掉。流氓不能进入警卫所在的牢房;
2. 其次,一些已经扔下的鞭炮可能会爆炸。形式上,如果鞭炮 $$$j$$$ 在第 $$$T$$$ 秒掉落,那么它将在第 $$$(T + s_j)$$$ 秒爆炸(例如,如果 $$$s_j = 2$$$ 的鞭炮在第 $$$4$$$ 秒掉落,它将在第 $$$6$$$ 秒爆炸);
3. 最后,警卫将一间牢房移至离流氓更近的地方。如果警卫移动到流氓所在的牢房,流氓就会被抓住。
显然,由于走廊是有限的,流氓迟早会被抓住。他的目标是在他被抓住之前看到最多数量的鞭炮爆炸;也就是说,他会采取行动,以在他被抓住之前最大化爆炸的鞭炮数量。
如果流氓行为最佳,你的任务是计算此类鞭炮的数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例由两行组成。第一行包含四个整数 $$$n$$$、$$$m$$$、$$$a$$$ 和 $$$b$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le m \le 2 \cdot 10^5$$$; $$$1 \le a, b \le n$$$; $$$a \ne b$$$) — 走廊的大小,走廊的数量鞭炮,分别是流氓的初始位置和警卫的初始位置。
第二行包含 $$$m$$$ 整数 $$$s_1$$$, $$$s_2$$$, ..., $$$s_m$$$ ($$$1 \le s_i \le 10^9$$$),其中 $$$s_i$$$ 是第 $$$i$$$ 个鞭炮点燃后爆炸所需的时间。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数——流氓在被抓住之前可以爆炸的最大鞭炮数量。
示例
输入 #1
3 7 2 3 6 1 4 7 2 3 6 5 1 7 2 3 6 4 4
输出 #1
2 1 1
注意
在第一个测试用例中,流氓应该采取如下行动:
- 第二个1:放下第二个鞭炮,所以它会在第$$$5$$$秒爆炸。警卫移动到牢房$$$5$$$;
- 第二个 2:移至单元格 $$$2$$$。警卫移动到牢房$$$4$$$;
- 第二个3:放下第一个鞭炮,所以它会在第$$$4$$$秒爆炸。警卫移动到牢房$$$3$$$;
- 第二个 4:移至单元格 $$$1$$$。第一声鞭炮爆炸了。警卫移动到牢房$$$2$$$;
- 第二个 5:留在单元格 $$$1$$$ 中。第二声鞭炮爆炸了。警卫移动到牢房 $$$1$$$ 并抓住了流氓。