LCC '22 Contest 3 J2 - She Sells Sea Shells by the Seashore

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Sunny runs a seashell store by the beach. On a beautiful summer day, she collected N seashells to be sold. Sunny determines that the i-th seashell she collected has a value of a_i.

To make the seashells look more appealing, she will arrange N-1 seashells in a circle, and place one seashell in the middle of the circle.

Sunny considers an arrangement outstanding if the value of the seashell in the middle is strictly greater than the mean value of the N-1 other seashells.

She wonders how many different seashells of hers can be placed into the middle that form an outstanding arrangement. Can you help her?

Constraints

For all subtasks,

1 \le N \le 10^6

1 \le a_i \le 10^9

Subtask 1 [55%]

1 \le N, a_i \le 2 \times 10^3

Subtask 2 [45%]

No additional constraints.

Input Specification

The first line of input will contain N.

The next line will contain N space-separated integers a_i.

Output Specification

Output one integer on one line, the number of different seashells that can be placed into the middle that form an outstanding arrangement.

Sample Input

5
1 4 6 3 6

Sample Output

2

Explanation

The only seashells that can form an outstanding arrangment are seashells 3 and 5. Note that seashell 2 cannot because the value of it (4) is not strictly greater than the mean of the other seashells (4).


Comments

There are no comments at the moment.