The problem requires us to count the number of intervals in the array ~A~ which contain a "dominant" element, that is, a number which appears more times than all the other numbers combined.

To solve the first subtask, it was sufficient to make a brute-force solution in ~\mathcal O(n^3)~ which iterates over all the intervals and checks if there is a dominant element. Solving the second subtask requires speeding this solution up to work in ~\mathcal O(n^2)~. One way to do this was to fix the left end of the interval, and while the right end is moving to the right, we keep track of the number of elements in the segment and check to see if there is a dominant element.

To solve the problem entirely, for each value, we'll count the number of segments in which this value is dominant. Fix some value ~x~ and make a new array ~B~ which consists of the numbers ~1~ and ~-1~. Here, ~1~ denotes that ~x~ is located in the array ~A~ at this position, and ~-1~ that it is not. Now, the number of intervals in which ~x~ is dominant is equal to the number of intervals in ~B~ which have a positive sum. This can be counted by making an array of prefix sums (call it ~C~) and for each element of ~C~, we count how many elements in ~C~ before it are smaller than it. However, we do not need to iterate over all elements in ~C~. For a block of ~-1~'s in ~B~, we can calculate at once the number of intervals with positive sum for which the right end is in this block. This can be done with a segment tree with propagation, where the nodes store, apart from the usual sum, the sum of the elements multiplied by ~k, k-1, \dots, 2, 1~ (~k \cdot \text{first_element} + (k-1) \cdot \text{second_element} + \dots + 1 \cdot \text{last_element}~), where ~k~ is the number of elements covered by the segment tree node. The complexity of this solution is ~\mathcal O(n \log n)~, but to score all of the points, it was possible to have other complexities, such as ~\mathcal O(n \sqrt n)~.