URI Online Judge | 2084


By Leopoldo Taravilse, Universidad Nacional de La Plata AR Argentina

Timelimit: 1

Right now presidential elections are being held in Nlogonia. For a candidate to win in the first round, he should obtain more votes than each of the other candidates. But that is not enough: he should also obtain at least 45% of all the votes, or at least 40% of all the votes and at least 10% more votes than each of the other candidates. This 10% has to be calculated from all votes. If no candidate wins in the first round, a new election is held as a second round.

Benicio is a political journalist in Nlogonia, and he always wants to scoop everyone else. This is why he has collected information from polls, and wants to know if according to these one of the candidates will win in the first round, or on the contrary there will be a second round. Benicio needs to decide this with haste, before someone else scoops him. Can you help him?


The first line contains an integer number N, representing the number of candidates (2 ≤ N ≤ 10). The second line contains Ninteger numbers Vi representing the amount of votes obtained by each of the candidates (0 ≤ Vi ≤ 1000 for i = 1, ..., N). At least one candidate obtained at least one vote, and there are no two candidates with the same number of votes.


Print a line containing a single digit, indicating if there is a winner in the first round or not. If there is such a first round winner, the digit must be a '1'; otherwise (i.e. if there should be a second round) the digit must be '2'.

Input Samples Output Samples


60 40



16 28 21



42 23 35