Calculating grades

Interview

Time limit1sMemory limit1024 MB

Summary

Given N scores from 0 to 100, count how many students receive each Suneung grade from 1 to 9 using the cumulative-share cutoffs.

Level: Easy3 of 10
Topics: Implementation, Prefix sum, Array
Solved: No attempts yet

Problem

Middle school grades are based on absolute evaluation, but you, a student at Dongnae High School, receive relative grades from 1 to 9 for both school grades and the college entrance exam (Suneung).

Chansol had nothing to do with the college entrance exam until he graduated from high school, so even now he does not know the detailed rules for calculating Suneung grades. Given the number of people who took one subject and the score each person received, write a program that counts how many students receive each grade from 1 to 9.

The Suneung grade cutoffs are as follows.

Grade	Cumulative share
1	Top 4% cumulative
2	Top 11% cumulative
3	Top 23% cumulative
4	Top 40% cumulative
5	Top 60% cumulative
6	Top 77% cumulative
7	Top 89% cumulative
8	Top 96% cumulative
9	Top 100% cumulative

Specifically, the grade cutoff score for grade 1 is the largest $i$ such that at least 4% of students scored between $i$ points and 100 points. Every student who scored $i$ or higher receives grade 1. Similarly, the grade cutoff score for grade 2 is the largest $j$ such that at least 11% of students scored between $j$ points and 100 points. Every student who scored below the grade 1 cutoff and at or above the grade 2 cutoff receives grade 2. If at least 11% of students scored at or above the grade 1 cutoff, then all of those students receive grade 1, and the grade 2 cutoff equals the grade 1 cutoff, so no student receives grade 2.

A grade blank means that no student receives that grade.

Input

The first line contains the number of people $N$ who took the subject.

The second line contains the scores $A_1, A_2, \cdots, A_N$ that each person received, separated by spaces.

Output

Print the number of students who receive grade 1, grade 2, $\cdots$ , grade 9, one per line.

If no student receives a given grade, print $0$ for that grade.

Constraints

$N=100$
$0 \leq A_i \leq 100$
All numbers in the input are integers.

Hint

The conditions for each grade are as follows.

Grade	Condition
1	(share of students above $x_1$ points)% $\lt$ 4%
2	4% $\leq$ (share of students above $x_2$ points)% $\lt$ 11%
3	11% $\leq$ (share of students above $x_3$ points)% $\lt$ 23%
4	23% $\leq$ (share of students above $x_4$ points)% $\lt$ 40%
5	40% $\leq$ (share of students above $x_5$ points)% $\lt$ 60%
6	60% $\leq$ (share of students above $x_6$ points)% $\lt$ 77%
7	77% $\leq$ (share of students above $x_7$ points)% $\lt$ 89%
8	89% $\leq$ (share of students above $x_8$ points)% $\lt$ 96%
9	96% $\leq$ (share of students above $x_9$ points)%

A student who scores $x_i$ points, which meets the condition for grade $i$ , receives grade $i$ .

For example, suppose $N=100$ , 11 people scored 100, 1 person scored 99, and everyone else scored below 99. Since 0% of students scored above 100, the 11 students who scored 100 all receive grade 1. Since 11% of students scored above 99, the student who scored 99 receives grade 3, not grade 2. As in this example, a grade blank means that no student receives grade 2.

Examples2

Example 1

Input

100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

Expected output

Example 2

Input

100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100

Expected output