Schtiffles - Marbl

⠀

James is learning numbers, and he is having fun writing them on a huge blackboard, from left to right.

At the beginning, James writes the number $$$1$$$.
Right after, James writes $$$1$$$ again, and then $$$2$$$.
Then James writes $$$1$$$, $$$2$$$, $$$3$$$.
$$$\ldots$$$
In the end, James writes $$$1$$$, $$$2$$$, $$$3$$$, $$$\ldots$$$, $$$n$$$.

For example, for $$$n = 5$$$, the numbers written by James make the array $$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$$.

James has a list of favorite numbers $$$a_1, a_2, \ldots, a_m$$$, and he wants to calculate how many subarrays of the array $$$b$$$ are equal to $$$a_1, a_2, \ldots, a_m$$$. $$$^{\text{∗}}$$$

James is already sure that $$$a_1, a_2, \ldots, a_m$$$ is a subarray of $$$b$$$, so the answer is at least $$$1$$$.

$$$^{\text{∗}}$$$The subarrays of an array $$$[v_1, v_2, \ldots, v_k]$$$ are generated as follows: for each $$$l, r$$$ such that $$$1 \leq l \leq r \leq k$$$, the array $$$[v_l, v_{l+1}, \ldots, v_r]$$$ is a subarray. So there are $$$k(k+1)/2$$$ subarrays in total, and some of them may be equal.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 200$$$) — the maximum number written by James, and the length of the array $$$a_1, a_2, \ldots, a_m$$$.

The second line of each test case contains $$$m$$$ integers $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \leq a_i \leq 10^5$$$) — James' favorite numbers.

It is guaranteed that for the given input, the answer is always at least $$$1$$$.

Note that there are no constraints on the sum of $$$n$$$ and $$$m$$$ over all test cases.

Output

For each test case, output a single line containing an integer: the number of subarrays of the array $$$b$$$ which are equal to $$$a_1, a_2, \ldots, a_m$$$.

Note

In the first test case, the blackboard contains the numbers

$$$$$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4]$$$$$$

and James has only one favorite number: the number $$$1$$$. There are $$$4$$$ subarrays of $$$b$$$ equal to $$$[1]$$$ (highlighted in red):

$$$[\color{red}{1}, 1, 2, 1, 2, 3, 1, 2, 3, 4]$$$;
$$$[1, \color{red}{1}, 2, 1, 2, 3, 1, 2, 3, 4]$$$;
$$$[1, 1, 2, \color{red}{1}, 2, 3, 1, 2, 3, 4]$$$;
$$$[1, 1, 2, 1, 2, 3, \color{red}{1}, 2, 3, 4]$$$.

In the second test case, the blackboard contains the numbers

$$$$$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$$$$$

and James's list of favorite numbers is $$$[1, 2, 3]$$$. There are $$$3$$$ subarrays of $$$b$$$ equal to $$$[1, 2, 3]$$$ (highlighted in red):

$$$[1, 1, 2, \color{red}{1, 2, 3}, 1, 2, 3, 4, 1, 2, 3, 4, 5]$$$;
$$$[1, 1, 2, 1, 2, 3, \color{red}{1, 2, 3}, 4, 1, 2, 3, 4, 5]$$$;
$$$[1, 1, 2, 1, 2, 3, 1, 2, 3, 4, \color{red}{1, 2, 3}, 4, 5]$$$.

In the third test case, the blackboard contains the numbers

$$$$$$b = [1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$$$$$$

and James's list of favorite numbers is $$$[3, 1, 2, 3, 4, 1]$$$. There is only $$$1$$$ subarray of $$$b$$$ equal to $$$[3, 1, 2, 3, 4, 1]$$$ (highlighted in red):

$$$[1, 1, 2, 1, 2, \color{red}{3, 1, 2, 3, 4, 1}, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6]$$$.

Idx	Name	Rating	Status
A	Incremental Subarray	800
C	Incremental Stay	1400

Codeforces Round 1053 (Div. 2)