Вам дан набор из $$$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$$$ | — |
44 2 3 1
10
21 3
4
