TAP2012I - In Debt

[The original version of this problem (in Spanish) can be found at http://www.dc.uba.ar/events/icpc/download/problems/taip2012-problems.pdf]

Ignacio and Ines really like science. Luckily they live in Nlogonia, where as everyone 
knows there are N science museums. Both Ignacio and Ines have the next N Saturdays free, 
so they have agreed on a schedule to visit a different science museum each of these 
days.
Ignacio is quite stingy, so that every Saturday he will tell Ines that he has forgotten 
to bring the money to pay the museum's entrance fee, and ask her to pay for him. Ines 
always does so, and because she knows him well she also knows that if she does ask for 
her money back, he will never pay up. In fact, Ines is certain that even if she asks 
Ignacio for her money back, he will only accept to pay if the cumulative debt is a 
multiple of 100, because otherwise he will argue that he has no change to pay exactly, 
and thus pays nothing at all.
This being the situation, every Sunday if the cumulative debt is a multiple of 100 Ines 
will go to Ignacio's house to claim her money, and because he'll have no excuse left, he 
will pay without any type of protest. Of course he doesn't like this, but he is comforted 
by the idea that if the cumulative debt after visiting the N museums is not a multiple of 
100, Ines shall not claim the last part of her money.
Ines would like to know how many times she will go to Ignacio's house to ask for her 
money. In order to calculate this, she can provide a list of the prices of the entrance 
fees to the N science museums in Nlogonia, in the order that she and Ignacio are going to 
visit them.

Ignacio and Ines really like science. Luckily they live in Nlogonia, where as everyone knows there are N science museums. Both Ignacio and Ines have the next N Saturdays free, so they have agreed on a schedule to visit a different science museum each of these days.

Ignacio is quite stingy, so every Saturday he will tell Ines that he has forgotten to bring the money to pay the museum's entrance fee, and will therefore ask her to pay for him. Ines always does so, and because she knows him well she also knows that unless she asks for her money back, he will never pay up. In fact, Ines is certain that even if she asks Ignacio for her money back, he will only accept to pay if the cumulative debt is a multiple of 100, because otherwise he will argue that he has no change to pay exactly, and will thus pay nothing at all.

This being the situation, every Sunday if the cumulative debt is a multiple of 100 Ines will go to Ignacio's house to claim her money, and because he'll have no excuse left, he will pay without any type of protest. Of course he doesn't like this, but he is comforted by the idea that if the cumulative debt after visiting the N museums is not a multiple of 100, Ines shall not claim the last part of her money.

Ines would like to know how many times she will have to go to Ignacio's house to ask for her money. In order to calculate this, she can provide a list of the prices of the entrance fees to the N science museums in Nlogonia, in the order that she and Ignacio are going to visit them.

Input

Each test case is described using two lines. The first line contains a single integer number N, indicating the number of science museums in Nlogonia (1 ≤ N  100). The second line contains N integers Pi representing the prices of the entrance fees to the different museums, in the order in which they are going to be visited ( Pi  100 for i = 1, ..., N). The end of the input is signalled by a line containing the number -1.

Output

For each test case, you should print a single line containing an integer number, representing the number of times Ines is going to have to go by Ignacio's house to ask for her money.

Example

Input:
3
50 50 50
5
50 100 100 100 100
9
25 50 75 100 25 50 75 100 25
5
35 45 20 22 33
3
100 100 100
-1

Output:
1
0
2
1
3

Added by:Fidel Schaposnik
Date:2012-10-04
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Argentinian Programming Tournament 2012

hide comments
2012-10-10 20:06:05 :D
Sorry, way too straight forward for classical.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.