C. Два цвета
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп установил новый забор на своей даче. Забор представляет собой $$$n$$$ досок одинакового размера, выставленных в ряд.

Монокарп решил, что покрасит свой забор по следующим правилам:

  • каждая доска забора будет покрашена ровно в один цвет;
  • количество различных цветов, в которые будут покрашены доски забора, равно ровно двум;
  • доски забора, которые будут покрашены в одинаковый цвет, должны образовывать непрерывную последовательность, то есть для всех пар досок забора, которые будут покрашены в одинаковый цвет, верно, что между ними не будет ни одной доски, покрашенной в другой цвет.

У Монокарпа есть $$$m$$$ различных красок, причем краски $$$i$$$-го цвета хватит для покраски не более $$$a_i$$$ досок забора. Докупать никакие краски Монокарп не будет.

Перед вами стоит задача определить количество различных способов покраски забора, которые удовлетворяют всем описанным пожеланиям Монокарпа. Два способа покраски считаются различными, если существует доска, которая покрашена в разные цвета в данных способах.

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$) — количество досок в заборе и количество различных цветов красок, которые есть у Монокарпа.

Во второй строке записаны $$$m$$$ целых чисел $$$a_1, a_2, \dots, a_m$$$ ($$$1 \le a_i \le n$$$), где $$$a_i$$$ равно максимальному количеству досок, на покраску которых хватит краски с цветом $$$i$$$.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите количество различных способов покраски забора, которые удовлетворяют всем описанным пожеланиям Монокарпа.

Пример
Входные данные
3
5 2
2 4
5 2
3 4
12 3
5 9 8
Выходные данные
4
6
22
Примечание

В первом наборе входных данных существует $$$4$$$ различных способа покраски забора (указаны последовательности номеров цветов, в которые могут быть покрашены доски забора в порядке слева направо):

  1. $$$[1, 2, 2, 2, 2]$$$;
  2. $$$[1, 1, 2, 2, 2]$$$;
  3. $$$[2, 2, 2, 1, 1]$$$;
  4. $$$[2, 2, 2, 2, 1]$$$.

Во втором наборе существует $$$6$$$ различных способов покраски забора (указаны последовательности номеров цветов, в которые могут быть покрашены доски забора в порядке слева направо):

  1. $$$[1, 2, 2, 2, 2]$$$;
  2. $$$[1, 1, 2, 2, 2]$$$;
  3. $$$[1, 1, 1, 2, 2]$$$;
  4. $$$[2, 2, 1, 1, 1]$$$;
  5. $$$[2, 2, 2, 1, 1]$$$;
  6. $$$[2, 2, 2, 2, 1]$$$.