Дана квадратная матрица, состоящая из $$$n$$$ строк и $$$n$$$ столбцов ячеек, оба пронумерованы от $$$1$$$ до $$$n$$$. Ячейки раскрашены в белый или черный цвет. Ячейки с $$$1$$$ до $$$a_i$$$ черные, а ячейки с $$$a_i+1$$$ до $$$n$$$ белые, в $$$i$$$-м столбце.
Вы хотите разместить $$$m$$$ целых чисел в матрице, от $$$1$$$ до $$$m$$$. Есть два правила:
Красота матрицы — это количество таких $$$j$$$, что $$$j+1$$$ написано в той же строке, в следующем столбце от $$$j$$$ (в соседней справа ячейке).
Чему равна максимальная красота матрицы?
В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — размер матрицы.
Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — количество черных клеток в каждом столбце.
В третьей строке записано одно целое число $$$m$$$ ($$$0 \le m \le \sum \limits_{i=1}^n n - a_i$$$) — количество чисел, которые требуется разместить в матрице. Обратите внимание, что это число может не поместиться в 32-битный целый тип данных.
Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
На каждый набор входных данных выведите одно целое число — максимальную красоту матрицы после того, как вы разместите в ней все $$$m$$$ целых чисел. Обратите внимание, что дается не больше чисел, чем белых клеток в матрице, так что ответ всегда существует.
630 0 0942 0 3 1542 0 3 1642 0 3 110100 2 2 1 5 10 3 4 1 120110
6 3 4 4 16 0
Название |
---|