You are given a set of $$$n$$$ weights, where $$$a_i$$$ is the weight of the $$$i$$$-th weight. In the store, there is an infinite number of products of each natural weight.
You only have balance scales in your store, where you can place products on the right pan and weights on the left pan. Your task is to determine the maximum weight $$$p$$$ such that any product in the store that weighs no more than $$$p$$$ can be uniquely (that is, you can guarantee to say what the weight of a particular product is) determined using the given balance scales for an unlimited number of weighings.
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of weights at your disposal.
The second line of input contains $$$n$$$ numbers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the weights available to you.
In a single line of output, you need to print one number, the maximum weight $$$p$$$. If you cannot uniquely determine the weight of any product, you should output $$$0$$$.
| № | Add. constraints | Points | Req. groups | Comment | |
| $$$n$$$ | $$$a_i$$$ | ||||
| $$$0$$$ | — | — | — | — | Tests from the statement |
| $$$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$$$ | — | — |
| $$$5$$$ | — | — | $$$27$$$ | $$$0-4$$$ | — |
44 2 3 1
10
21 3
4
