Let us consider an infinite sequence of stacks indexed from $0,$ and an exchange operation that removes two tokens from a stack and adds one token to the next stack.

For example, lets assume there are two tokens on stack $0$ and three on stack $1.$ Two tokens from stack $0$ may be exchanged for one new token on stack $1.$ After that operation, there are four tokens on stack $1$ that may be exchanged for two new tokens on stack $2.$ Finally, a new token may be added to stack $3$ by exchanging two tokens from stack $2.$ This gives us: stacks $0,1$ and $2$ empty, and stack $3$ with one token.

Given the heights of the first N stacks, find the minimum number of tokens that may remain after any number of exchange operations. You may assume that all of the tokens are identical. All uninitialized stacks are empty by default.

Write a function:

class Solution $\{$ public int solution $($int$[]$ A$)$; $\}$

that, given an array A of N integers, representing the heights of the first N stacks in the sequence, returns the minimum number of tokens which may remain on the stacks after any number of exchange operations.

Examples:

$1.$ Given A $=[2,3],$ the function should return $1,$ as explained above.

$2.$ Given A $=[1,0,4,1],$ the function should return $3.$ One token from stack $0$ cannot be exchanged. Then the four tokens from stack $2$ can be exchanged for two tokens on stack $3.$ In the end, two of the three tokens from stack $3$ can be exchanged for one token on stack $4.$ That gives us three tokens, one on each of the stacks $0,3$ and $4.$

$1$

$3.$ Given A $=[5],$ the function should return $2.$ Four of the five tokens from stack $0$ can be exchanged for two on stack $1,$ and then in turn for one token on stack $2.$ After that we have one token on each of stacks $0$ and $2.$

$4.$ Given A $=[4,0,3,0],$ the function should return $1.$ The four tokens from stack $0$ can be exchanged for two on stack $1,$ then for one token on stack $2.$ The four tokens that are now on stack $2$ can be exchanged for two on stack $3,$ then for one token on stack $4.$

Write an efficient algorithm for the following assumptions:

$$ N is an integer within the range $[1.\mathrm{.}100,000]$;

$$ each element of array A is an integer within the range $[0.\mathrm{.}1,000,000].$