B"Bear Limak has n colored balls, arranged in one long row. Balls are numbered 1 through n, from left to right. There are n possible colors, also numbered 1 through n. The i-th ball has color ti. For a fixed interval (set of consecutive elements) of balls we can define a dominant color. It's a color occurring the biggest number of times in the interval. In case of a tie between some colors, the one with the smallest number (index) is chosen as dominant. There are non-empty intervals in total. For each color, your task is to count the number of intervals in which this color is dominant. The first line of the input contains a single integer n (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n xe2 x80 x89 xe2 x89 xa4 xe2 x80 x895000) -- the number of balls. The second line contains n integers t1, xe2 x80 x89t2, xe2 x80 x89..., xe2 x80 x89tn (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89ti xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n) where ti is the color of the i-th ball. Print n integers. The i-th of them should be equal to the number of intervals where i is a dominant color. In the first sample, color 2 is dominant in three intervals: There are 7 more intervals and color 1 is dominant in all of them. "...