410184: GYM103969 D Splitting Jellybeans

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Splitting Jellybeanstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have meticulously collected all possible types of jellybeans and now you want to display them by splitting them into a series of piles.

Specifically, jellybeans have $$$N$$$ different qualities (size, color, taste, etc). Quality $$$i$$$ has $$$q_i$$$ options. Given that you have collected all the jellybeans, you own one example of every combination of each quality.

You have now decided to split them up so they can be put on display around the world. However, you're very concerned so you have adopted an interesting procedure. If possible, you divide the initial pile into two equally sized piles in the first round. In the next round, attempt to split each of these piles once again into equally sized piles. You then continue until this is no longer possible.

Given the number of qualities $$$N$$$ and the number of options for each quality, how many rounds will this process last?

Input

First Line: A single integer, $$$1 \leq N \leq 10^4$$$

Second Line: $$$N$$$ integers $$$1 \leq q_i \leq 10^4$$$

Output

The number of rounds the process will last.

ExampleInput
2
6 2
Output
2
Note

Since there are two qualities with $$$6$$$ and $$$2$$$ options respectively, there are $$$12$$$ total jellybeans in your collection.

Round 1: Split $$$12$$$ into two piles of $$$6$$$.

Round 2: Split the two piles of $$$6$$$ into four piles of $$$3$$$.

加入题单

算法标签: