Forming societies Solution

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 ats, 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 ats than any other building in the society has control of the society. If two buildings have equal number, neither has control. You have to nd 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 nd the number of substrings fj ; : : : ; fk such that j i k and fi is the unique maximum element in the substring.

A society of buildings from i to j, for i j, is said to be well-formed if building i has minimum number of ats in the society and building j has the maximum number. The maximum and minimum may not be unique in this case. In other words, fi is the minimum of the substring fi; : : : ; fj and fj is the maximum. A society with a single building is always well-formed. In the second part of the problem, you have to compute the total number of non-empty well-formed societies possible.

Input/ Output The rst line of input will specify n, the number of buildings, which will be at most 106. The next line will contain n positive integers giving the number of ats in each building. Each number will be at most 1000 and the numbers will be separated by a single space. The rst line of output should contain n numbers, the ith of which is the number of societies the ith building can control. The numbers should be printed on a single line separated by a space. The next line should contain the total number of well-formed socities. Note that the numbers may be large so use long long int type.

Sample Input
Sample Output
4


2
1
6 1
2
1 3
2
5



Note: For the second part, it may help to use the vector class from the C++ standard library. This is essentially an implementation of the sequence abstract data type, and allows many operations. The functions most useful here would be the push back function that adds an element at the end of the sequence, and the lower bound function de ned in the algorithm class, that nds the smallest element in a vector that is not less than a given element. You can read details about this online, at for example C++.com, in case you are not familiar with vectors. You can also do it with just arrays, but may have to implement binary search in that case. This is not required for the rst part. You will get half credit if you do the rst part correctly. Use the algorithm in the last quiz for this. Submission: Submit a single le named RollNo 6.cpp






1