Это простая версия задачи. Единственное отличие между двумя версиями — ограничение на $$$y$$$. В этой версии $$$y = 0$$$. Вы можете делать взломы, только если обе версии задачи решены.
Бесси получила от своей лучшей подруги Элси праздничный торт в виде правильного многоугольника с $$$n$$$ сторонами. Вершины торта пронумерованы от $$$1$$$ до $$$n$$$ по часовой стрелке. Вы с Бесси собираетесь выбрать некоторые вершины и сделать непересекающиеся разрезы по диагоналям торта так, чтобы концы разрезов входили в множество выбранных вершин.
Бесси хотела бы раздавать только те куски торта, которые являются треугольниками, чтобы всё было честно. Размеры кусков не имеют значения, и весь торт не обязательно должен быть разделен только на треугольники (в торте могут быть куски и других форм, но они не будут учитываться).
Бесси уже выбрала $$$x$$$ вершин, которые могут быть использованы как концы разрезов. Она хочет, чтобы вы выбрали не более $$$y$$$ других вершин так, чтобы количество треугольных кусков торта, которые она может раздать после разрезания, было максимальным.
Какое максимальное количество треугольных кусков торта может раздать Бесси?
В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных состоит из трех целых чисел $$$n$$$, $$$x$$$ и $$$y$$$ ($$$4 \leq n \leq 10^9$$$, $$$2 \leq x \leq \min(n, 2 \cdot 10^5)$$$, $$$y = 0$$$) — количество сторон многоугольника, количество вершин, которые выбрала Бесси, и максимальное количество других вершин, которые вы можете выбрать.
Вторая строка состоит из $$$x$$$ различных целых чисел от $$$1$$$ до $$$n$$$, представляющих собой вершины, которые выбрала Бесси.
Гарантируется, что сумма $$$x$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число: максимальное количество непересекающихся треугольных кусков торта, которые она может раздать.
38 4 01 6 2 58 8 01 3 2 5 4 6 7 84 2 01 3
2 6 2
В наборах входных данных $$$1$$$, $$$2$$$ и $$$3$$$ можно получить соответственно $$$2$$$, $$$6$$$ и $$$2$$$ непересекающихся треугольных куска торта. Возможные конструкции показаны на следующих рисунках:
Зеленые точки обозначают вершины, которые можно использовать, синие линии — диагонали, которые проводятся, а красные цифры — треугольники, которые подсчитываются.
