Joker
Contest: Codeforces Round 995 (Div. 3)
Difficulty rating: 2000
Tags: brute force, greedy, implementation, math

Consider a deck of $$$n$$$ cards. The positions in the deck are numbered from $$$1$$$ to $$$n$$$ from top to bottom. A joker is located at position $$$m$$$.

$$$q$$$ operations are applied sequentially to the deck. During the $$$i$$$-th operation, you need to take the card at position $$$a_i$$$ and move it either to the beginning or to the end of the deck. For example, if the deck is $$$[2, 1, 3, 5, 4]$$$, and $$$a_i=2$$$, then after the operation the deck will be either $$$[1, 2, 3, 5, 4]$$$ (the card from the second position moved to the beginning) or $$$[2, 3, 5, 4, 1]$$$ (the card from the second position moved to the end).

Your task is to calculate the number of distinct positions where the joker can be after each operation.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \le n \le 10^9$$$; $$$1 \le m \le n$$$; $$$1 \le q \le 2 \cdot 10^5$$$).

The second line contains $$$q$$$ integers $$$a_1, a_2, \dots, a_q$$$ ($$$1 \le a_i \le n$$$).

Additional constraint on the input: the sum of $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print $$$q$$$ integers — the number of distinct positions where the joker can be after each operation.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
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

Example output:
2 3 5 
2 2 2 2 
2 
2 3 3 3 
2 4 6 8

Editorial:
Let's represent the positions where the joker can be as a set of non-overlapping segments $$$[l_1, r_1]$$$, $$$[l_2, r_2]$$$, .... Let's consider what happens to the segment $$$[l, r]$$$ after applying the $$$i$$$-th operation:
• if $$$a_i < l$$$, the possible positions segment becomes $$$[l - 1, r]$$$ (since moving the $$$a_i$$$-th card to the front does not change the joker's positions, while moving it to the back shifts the positions up by $$$1$$$);
• if $$$a_i > r$$$, the possible positions segment becomes $$$[l, r + 1]$$$ (since moving the $$$a_i$$$-th card to the front shifts the positions down by $$$1$$$, while moving it to the back does not change the joker's positions);
• if $$$l \le a_i \le r$$$, let's consider $$$3$$$ subsegments where the joker can be located:   positions from the subsegment $$$[l, a_i - 1]$$$ moves to $$$[l, a_i]$$$ (similarly to the case $$$a_i > r$$$);  positions from the subsegment $$$[a_i + 1, r]$$$ moves to $$$[a_i, r]$$$ (similarly to the case $$$a_i < l$$$);  the joker from position $$$a_i$$$ moves to one of two positions: $$$1$$$ or $$$n$$$.  Thus, in this case, the segment $$$[l, r]$$$ remains, but we need to add two new segments ($$$[1, 1]$$$ and $$$[n, n]$$$) to the set.
• positions from the subsegment $$$[l, a_i - 1]$$$ moves to $$$[l, a_i]$$$ (similarly to the case $$$a_i > r$$$);
• positions from the subsegment $$$[a_i + 1, r]$$$ moves to $$$[a_i, r]$$$ (similarly to the case $$$a_i < l$$$);
• the joker from position $$$a_i$$$ moves to one of two positions: $$$1$$$ or $$$n$$$.
Note that when $$$l=r=a_i$$$, the current segment disappears.
At first glance, it seems that this solution works in $$$O(nq)$$$, since the number of segments can be $$$O(n)$$$, and we need to update each of them. However, it is not difficult to notice that there cannot be more than $$$3$$$ segments. Specifically: the initial segment $$$[m, m]$$$, which expands to the left and right, the segment $$$[1,1]$$$, which expands only to the right, and the segment $$$[n, n]$$$, which expands only to the left.