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

Назовем $$$k$$$-ступенчатой лестницей следующую конструкцию: ровно $$$k + 2$$$ деревянные доски, среди которых

  • две доски длиной хотя бы $$$k+1$$$ — основные направляющие лестницы;
  • $$$k$$$ досок длиной хотя бы $$$1$$$ — ступеньки лестницы.

Заметим, что ни направляющие, ни ступени не обязаны быть равны.

Например, лестницы $$$1$$$ и $$$3$$$ — корректные $$$2$$$-ступенчатые лестницы, а лестница $$$2$$$ — корректная $$$1$$$-ступенчатая. На первом изображении длины досок равны $$$[3, 3]$$$ для направляющих и $$$[1]$$$ для ступеньки. На втором изображении длины досок равны $$$[3, 3]$$$ для направляющих и $$$[2]$$$ для ступеньки. На третьем изображении длины досок равны $$$[3, 4]$$$ для направляющих и $$$[2, 3]$$$ для ступенек.

У вас есть $$$n$$$ досок. Длина $$$i$$$-й доски равна $$$a_i$$$. У вас нет пилы и вы не можете распиливать доски. Зато есть молоток и гвозди, и вы можете собрать импровизированную «лестницу» из тех досок, что есть.

Вопрос в следующем: чему равно максимальное $$$k$$$ такое, что вы сможете собрать $$$k$$$-ступенчатую лестницу, используя некоторый поднабор из имеющихся досок?

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

В первой строке задано единственное число $$$T$$$ ($$$1 \le T \le 100$$$) — количество запросов. Все запросы независимы.

Каждый запрос состоит из двух строк. В первой строке задано одно число $$$n$$$ ($$$2 \le n \le 10^5$$$) — количество досок у вас в наличии.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$) — длины соответствующих досок.

Гарантируется, что суммарное количество досок во всех запросах не превосходит $$$10^5$$$.

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

Выведите $$$T$$$ чисел — по одному на запрос. $$$i$$$-е число обозначает максимальное $$$k$$$ такое, что вы можете собрать $$$k$$$-ступенчатую лестницу из досок описанных в $$$i$$$-м запросе.

Выведите $$$0$$$, если невозможно собрать даже $$$1$$$-ступенчатую лестницу из заданных досок.

Пример
Входные данные
4
4
1 3 1 3
3
3 3 2
5
2 3 3 4 2
3
1 1 2
Выходные данные
2
1
2
0
Примечание

Варианты лестниц для запросов $$$1-3$$$ представлены на картинке выше:

О качестве полученных лестниц: