Most of the sorting algorithms we studied so far are comparison$-$based sorting. That means these algorithms sort a list by comparing the elements to one another. The worst$-$case running time of a comparison sort cannot be lower than N log$($ N$),$ where N is the number of inputs, as this is the minimum number of comparisons necessary to know where to put each element in the list.

There is a more efficient sorting algorithm for certain types of inputs. When a list contains elements from a certain range of values, it is possible to sort lists by counting the frequency of the elements.

In this lab, you will write a program that will count how many times an element appears in a list of numbers.

Input

The input will be in the following format:

$-$ In line $1,$ you will be given the size $($say N$)$ of the list of numbers.

$-$ In line $2,$ there will be N space$-$separated numbers that belong to the list.

Output

$-$ Your output will be the number of times each number appears on the list.

Sample Input

$50$

$699788827377898579778788657973959183569795756784851356212195145332328157911455393113414411$

Sample output

$3111111010111010001000100001001010000010100110000010001100000000101010002010202001112012101000202$

Explanation

The output prints the number of times each number appears in the list. $1$ appears $3$ times, $2$ appears $1$ time, $97$ appears $2$ times, etc.

CountingSort.java

import java.util.$*$;

public class CountingSort $\{$

static int$[]$ countingSort$($int$[]$ array$)\{$

$//$ Complete this method

$\}$

public static void main$($String$[]$ args$)\{$

Scanner in $=$ new Scanner$($System$.$in$)$;

$//$ Read the number of inputs

int n $=$ in$.$nextInt$()$;

int$[]$ array $=$ new int$[$n$]$;

$//$ Read the inputs into an array

for$($int i $=0$; i $<$ n; i$++)\{$

array$[$i$]=$ in$.$nextInt$()$;

$\}$

$//$ result will contain the counts of the numebrs

int$[]$ result $=$ countingSort$($array$)$;

for $($int i $=0$; i $<$ result.length; i$++)\{$

System.out.print$($result$[$i$]+($i $!=$ result.length $-1?""$ : $""))$;

$\}$

System.out.println$()$;

in$.$close$()$;

$\}$

$\}$