Назовем \(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\) чисел — по одному на запрос. \(i\)-е число обозначает максимальное \(k\) такое, что вы можете собрать \(k\)-ступенчатую лестницу из досок описанных в \(i\)-м запросе.
Выведите \(0\), если невозможно собрать даже \(1\)-ступенчатую лестницу из заданных досок.