A long street has n buildings in a row, located on one side of the street, numbered sequentially from 0 to n − 1. The ith building has fi flats, for 0 ≤ i < n. Some of the building residents want to join together to form a co-operative housing society. A restriction imposed is that buildings in a society must occur consecutively along the street, that is, should be numbered from i to j for some 0 ≤ i ≤ j < n. In a society, the building that has more flats than any other building in the society has control of the society. If two buildings have equal number, neither has control. You have to find for each building i, the number of distinct societies in which it will have control. More formally, given a sequence of numbers f0,...,fn−1, for each i, you have to find the number of substrings fj,...,fk such that j ≤ i ≤ k and fi is the unique maximum element in the substring.
Sample Input Sample Output
4 2 1 6 1
2 1 3 2 5
1
