Description

You are a player starting at Level 0 with 0 XP. You will perform N actions, and each action awards you a certain amount of experience points (XP).

The XP values for each type of actions are:

• Type 1: killing a zombie. You gain 10 XP.
• Type 2: killing a skeleton. You gain 15 XP.
• Type 3: using bottle of experience. You gain 100 XP.

 

Leveling Up Mechanism

To advance from your current level to the next, you must consume XP equal to the square of the target level.

• To reach Level 1 from Level 0, it costs 1² = 1 XP.

• To reach Level 2 from Level 1, it costs 2² = 4 XP.

• To reach Level 3 from Level 2, it costs 3² = 9 XP.

• In general, to reach Level L+1, you must spend (L+1)² XP.

As long as your current XP is enough to pay for the next level's cost, you must level up immediately and subtract the cost from your total XP. This process continues until you can no longer afford the next level.

 

Constraints

• For testcases 1~4, 0 <= N <= 100.
• For testcase   5,     0 <= N <= 20000.

 

Input

• The first line is an integer N, the number of actions.

• Then following by N lines, each containing a single number (1, 2, or 3), representing the action type.

Output

An integer representing the player's final level with '\n'.

Sample Input  Download

Sample Output  Download

Tags

Discuss