← 返回题目列表

Codeforces · 2051/F

F. 小丑

中文机器翻译题面 查看原题

考虑一副 $$$n$$$ 牌。牌组中的位置从上到下编号为 $$$1$$$ 到 $$$n$$$。小丑位于 $$$m$$$ 位置。

$$$q$$$ 操作按顺序应用于牌组。在第 $$$i$$$ 操作中,您需要在位置 $$$a_i$$$ 处取出卡片并将其移动到牌组的开头或末尾。例如,如果牌组是$$$[2, 1, 3, 5, 4]$$$,并且$$$a_i=2$$$,则操作后牌组将是$$$[1, 2, 3, 5, 4]$$$(第二个位置的牌移动到开头)或$$$[2, 3, 5, 4, 1]$$$(第二个位置的牌移动到开头)结束)。

你的任务是计算每次操作后小丑可以所处的不同位置的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le m \le n$$$; $$$1 \le q \le 2 \cdot 10^5$$$)。

第二行包含 $$$q$$$ 整数 $$$a_1, a_2, \dots, a_q$$$ ($$$1 \le a_i \le n$$$)。

对输入的附加约束:所有测试用例的 $$$q$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$q$$$ 整数 - 每次操作后小丑可以所处的不同位置的数量。

示例

输入 #1

5
6 5 3
1 2 3
2 1 4
2 1 1 2
5 3 1
3
3 2 4
2 1 1 1
18 15 4
13 15 1 16

输出 #1

2 3 5 
2 2 2 2 
2 
2 3 3 3 
2 4 6 8