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