У медвежонка Лимака есть n цветных шаров, выложенных в ряд. Шары пронумерованы от 1 до n слева направо. Всего существует n различных цветов, также пронумерованных от 1 до n. Цвет i-го слева шара равен ti.
Для каждого отрезка (множества расположенных подряд) шаров определим доминирующий цвет. Таким цветом назовём тот, который встречается на данном отрезке больше всего раз. В случае, если таких цветов несколько, доминирующим называется тот из них, номер (индекс) которого минимален.
Всего существует 
непустых отрезков. Для каждого цвета вычислите количество отрезков, на которых он является доминирующим.
Выходные данные
Выведите n целых чисел, i-е из которых должно равняться количеству отрезков, на которых цвет i является доминирующим.
Примечание
В первом примере цвет 2 является доминирующим на трёх отрезках:
- Отрезок [2, 2] содержит один шар. Этот шар имеет цвет 2, так что, конечно, 2 является доминирующим цветом для этого отрезка.
- Отрезок [4, 4] также содержит один шар, и цвет этого шара — 2.
- Отрезок [2, 4] содержит два шара цвета 2 и один шар цвета 1.
На остальных 7 отрезках доминирующим является цвет 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2 1 2
|
7 3 0 0
|
|
2
|
3
1 1 1
|
6 0 0
|