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

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. 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?

Input

The first line contains an integer number N, representing the number of candidates (2 ≤ N ≤ 10). The second line contains N integer numbers V_i representing the amount of votes obtained by each of the candidates (0 ≤ V_i ≤ 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.

Output

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'.

Example 1

Input:
2
60 40

Output:
1

Example 2

Input:
3
16 28 21

Output:
1

Example 3

Input:
3
42 23 35

Output:
2

Example 4

Input:
3
297 302 401

Output:
2