#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## Problem Description

Ronza is a traveling merchant. The king allows her to sell exotic goods from her traveling shoppe, an airship. When she enters a region her location is an area available to hunters. Not much is known about her, though rumors are that she comes back on special occasions such as giveaways.

This year, Ronza has *N* types of traps in stock, with infinite quantities of each type. The *i*th trap costs *A _{i}* gold, in

**strictly increasing order**.

Jianzhi is playing mousehunt! He is addicted to mousehunt so he is willing to obtain **as much gold as he wants** to purchase Ronza's traps. Just as usual, Jianzhi is busy with his studies, so he has coded a bot to help him to purchase some of Ronza's *N* Limited Editition traps.

Jianzhi can only use the bot once after choosing the amount of gold the bot starts with, then the bot purchases traps greedily. The bot will buy the most expensive trap it can repeatedly. Jianzhi is a huge fan of limited edition mousehunt traps and wants to know the maximum number of distinct types of traps he can buy among the all possible starting gold values.

As a reference, below is a pseudo-code of Jianzhi's greedy bot:

Let A be the amount of money Jianzhi is left with and B be the most expensive which value does not exceed A. void buytraps(A) { if(there are no such values of B)return; buy trap with cost B buytraps(A-B); }

## Limits

For all tests: A_{i} is strictly increasing. All variables are positive integers, and **1-indexed**.

Subtask 1 (15%): N ≤ 100, A_{i} ≤ 10000.

Subtask 2 (24%): N ≤ 2000, A_{i} ≤ 1000000.

Subtask 3 (61%): N ≤ 200000, A_{i} ≤ 10^{18}.

Subtask 4 (0%): Sample Testcases.

## Input

The first line of input will contain one integer, *N*.

The second line of input will contain *N* integers, representing the array *A*.

## Output

Output the maximum number of types of traps Jianzhi's bot can buy.

## Sample Testcase 1

### Input

6 1 2 4 8 16 32

### Output

6

### Explanation

Jianzhi can start with 63 gold = 1 + 2 + 4 + 8 + 16 + 32.

## Sample Testcase 2

### Input

6 1 3 6 8 15 20

### Output

4

### Explanation

Jianzhi can start with 39 gold = 1 + 3 + 15 + 20.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 15 | 22 | 1s | 256MB | Minimum |

2 | 24 | 42 | 1s | 256MB | Minimum |

3 | 61 | 62 | 1s | 256MB | Minimum |

4 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-8 ans.cpp -o ronza -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512