B. Космический корабль
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан набор из $$$n$$$ гирек, где $$$a_i$$$ — вес $$$i$$$-й гирьки. В магазине есть бесконечное количество товаров каждого натурального веса.

У вас в магазине есть только чашечные весы, на правую чашу которых вы можете класть только товар, а на левую чашу только гирьки. Вашей задачей является определить такой максимальный вес $$$p$$$, что любой товар в магазине, который весит не более $$$p$$$, можно однозначно (то есть вы гарантированно можете сказать, какой вес у того или иного товара) определить с помощью данных чашечных весов за неограниченное количество взвешиваний.

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

В первой строке входных данных вводится единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество гирек в вашем распоряжении.

Во второй строке входных данных вводится $$$n$$$ чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — веса гирек в вашем распоряжении.

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

В единственной строке выходных данных вам нужно вывести одно число, максимальный вес $$$p$$$. Если вы не можете однозначно определить вес ни одного товара, следует вывести $$$0$$$.

Система оценки
№Доп. ограниченияБаллыНеобх. подгруппыКомментарий
$$$n$$$$$$a_i$$$
$$$0$$$————Тесты из условия
$$$1$$$—$$$a_i \le i$$$$$$8$$$——
$$$2$$$$$$n \le 18$$$—$$$12$$$——
$$$3$$$$$$n \le 100$$$$$$\sum a_i \le 10^4$$$$$$17$$$——
$$$4$$$$$$n \le 1000$$$$$$a_i \le 1000$$$$$$36$$$$$$3$$$—
$$$5$$$——$$$27$$$$$$0-4$$$—
Примеры
Входные данные
4
4 2 3 1
Выходные данные
10
Входные данные
2
1 3
Выходные данные
4