Pyramid — Eolymp

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5 ) — the number of boxes.

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $1 \leq a_{i} \leq 1 0^{9}$ 1 \le a_i \le 10^9) — their weights.

Output

Output a single integer — the maximum possible number of boxes in one pyramid.

Examples

Example 1

Loading

Example 2

Loading

Note

In the first example, you can put a box with weight $1$ on top of the box with weight $2$ , because $1 \cdot 2 \leq 2$ 1\cdot2 \le 2.

In the second example, you can put a box with weight $1$ on top of the box with weight $2$ , because $1 \cdot 2 \leq 2$ 1\cdot2 \le 2. These two boxes can then be put on top of the box with weight $6$ , because $(1 + 2) \cdot 2 \leq 6$ (1+2)\cdot2 \le 6.

Scoring

Solutions that work if $1 \leq n \leq 1000$ 1 \le n \le 1\,000 will receive $30%$ of points.