Limits 1s, 512 MB

Flash is a fictional character in DC comics. He is regarded as the hero who can run and heal fast. Sometimes he can run faster than light and thus travels time. Cool huh ...!!! There is also another thing.

In Flash's story line, Cisco and Dr. Martin Stein at S.T.A.R. lab explores multiverse theory where in different universes, there is a different Flash. But being Thanos , you have just grabbed all the infinity stones. Now you have the power to do anything. So you move to DC universe to have a taste of their heroes. At your pleasure DC universe is arranging a tournament so that you may not destroy their half of the universe.

You have regrouped all the Flashes from all the universes. Now you are arranging a tournament where all the Flashes will participate in a race. The rules of the tournament are the following:

  • There will be no tie for a single match.
  • If N Flashes are participating, the champion will gain N points. The runner up will gain (N-1) point and so on (means the Flash who stood Nth position will get 1 point).
  • The whole championship could be won by multiple person if they get equal points.

Now Thanos has to fight with Superman while the championship runs. So after defeating Superman, you find that the last race of the tournament is running. In the mean time Cisco Ramon a.k.a The Vibe creates a point table as he already saw the future that if you get angry you may destroy the half of the universe. You have the point table of the whole championship till now. You are curious about how many Flashes have the chance to win the tournament. Being an upper class cosmic entity, you may consider all possible outcomes.

Note: Mixing superheros of DC and Marvel is not a crime. It's a dream come true.

Input

For each case, there will be a single integer, N denoting the total number of Flashes that are participating. The next line will contain N positive space separated integers, describing the score of each Flash. Take input until EOF.

Constraints :

  • 3 ≤ N ≤ 300000
  • 0 ≤ score ≤ 2000000

Total number of test case should not be more than 10.

Output

For each test case, print a single integer denoting the answer.

Sample

InputOutput
3
1 2 3
3

Submit

Login to submit.

Statistics

52% Solution Ratio
maknunlakmeEarliest, May '18
steinumFastest, 0.0s
steinumLightest, 5.5 kB
Kheya_COUShortest, 426B
Toph uses cookies. By continuing you agree to our Cookie Policy.