Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Carrier

By flash_7 · Limits 2s, 512 MB

After a lot of chilling, Pikachu is determined to build his carrier. The sole purpose of his carrier is to count the number of times a carry is generated when a group of numbers are simultaneously added together. For example, when the 5 numbers 999, 999, 999, 999 and 999 are added together, the carrier will return 3.

You are his friend and you have no idea why Pikachu got this new whim. And of course, Pikachu is bad at maths and asked you to figure out the solution.

More formally, you will be given an array A of N integers. You have to find the number of times a carry will be generated if you simultaneously add them together.

Input

The first line of the input contains a single integer N. The next line contains N space separated integers.

Constraints:

1 ≤ N ≤ 100
0 ≤ Ai ≤ 1018

Output

Print a single integer which is the output of the carrier.

Samples

InputOutput
5
999 999 999 999 999
3
InputOutput
12
999 999 999 999 999 999 999 999 999 999 999 999
4
InputOutput
5
1 2 3 2 1
0

Explanation:

The following table shows the logic of the carrier for the 2nd sample input:

    Discussion

    Statistics


    86% Solution Ratio

    NirjhorEarliest, Jul '18

    syed_jafrulFastest, 0.0s

    mdvirusLightest, 0 B

    mdvirusShortest, 280B

    Submit

    Login to submit

    Related Contests

    Intra NSU Programming Contest Summer 2018 Ended at 2018-07-20 07:15:00 +0000 UTC
    Replay of Intra NSU Programming Contest Summer 2018 Ended at 2018-07-27 17:00:00 +0000 UTC