2075C. Two Colors

binary search, combinatorics, math, 1500, https://codeforces.com/contest/2075/problem/C

Monocarp has installed a new fence at his summer house. The fence consists of 𝑛 planks of the same size arranged in a row.

Monocarp decided that he would paint his fence according to the following rules:

each plank of the fence will be painted in exactly one color;
the number of different colors that the planks will be painted in is exactly two;
the planks of the fence that are painted in the same color must form a continuous sequence, meaning that for all pairs of planks painted in the same color, there will be no planks painted in a different color between them.

Monocarp has 𝑚 different paints, and the paint of the 𝑖-th color is sufficient to paint no more than 𝑎𝑖 planks of the fence. Monocarp will not buy any additional paints.

Your task is to determine the number of different ways to paint the fence that satisfy all of Monocarp's described wishes. Two ways to paint are considered different if there exists a plank that is painted in different colors in these two ways.

Input

The first line contains a single integer 𝑡 (1≤𝑡≤104) — the number of test cases.

The first line of each test case contains two integers 𝑛 and 𝑚 (2≤𝑛,𝑚≤2⋅105) — the number of planks in the fence and the number of different colors of paint that Monocarp has.

The second line contains 𝑚 integers 𝑎1,𝑎2,…,𝑎𝑚 (1≤𝑎𝑖≤𝑛), where 𝑎𝑖 is the maximum number of planks that can be painted with the paint of color 𝑖.

The sum of 𝑛 over all test cases does not exceed 2⋅105. The sum of 𝑚 over all test cases does not exceed 2⋅105.

Output

For each test case, output the number of different ways to paint the fence that satisfy all of Monocarp's described wishes.

Example

Input

Output

4
6
22

Note

In the first test case, there are 4 different ways to paint the fence (the sequences of color numbers in which the planks can be painted from left to right are listed below):

[1,2,2,2,2];
[1,1,2,2,2];
[2,2,2,1,1];
[2,2,2,2,1].

In the second test case, there are 6 different ways to paint the fence (the sequences of color numbers in which the planks can be painted from left to right are listed below):

[1,2,2,2,2];
[1,1,2,2,2];
[1,1,1,2,2];
[2,2,1,1,1];
[2,2,2,1,1];
[2,2,2,2,1].

使用m-bisect_left(a,k)找到能涂k个板子的颜色种类数目，然后初步数目为x*y，假设k>n-k，那么能涂k块的x种颜色一定也可以涂(n-k)块，也就是说x中包含了y，所以要减去min(x,y)，这些是用同一种颜色涂的方案数。

python

from bisect import bisect_left

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = sorted(list(map(int, input().split())))
    ans = 0
    for k in range(1, n):
        x = m - bisect_left(a, k)
        y = m - bisect_left(a, n - k)
        ans += x * y - min(x, y)
    print(ans)

2075C. Two Colors ​

2075C. Two Colors