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 ith trap costs Ai 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.
if(there are no such values of B)return;
buy trap with cost B
For all tests: Ai is strictly increasing. All variables are positive integers, and 1-indexed.
Subtask 1 (15%): N ≤ 100, Ai ≤ 10000.
Subtask 2 (24%): N ≤ 2000, Ai ≤ 1000000.
Subtask 3 (61%): N ≤ 200000, Ai ≤ 1018.
Subtask 4 (0%): Sample Testcases.
The first line of input will contain one integer, N.
The second line of input will contain N integers, representing the array A.
Output the maximum number of types of traps Jianzhi's bot can buy.
Sample Testcase 1
1 2 4 8 16 32
Jianzhi can start with 63 gold = 1 + 2 + 4 + 8 + 16 + 32.
Sample Testcase 2
1 3 6 8 15 20
Jianzhi can start with 39 gold = 1 + 3 + 15 + 20.