In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 21st
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #10 exercise sheet]
In this problem you should read from the standard input using functions such as input() and you should write to the standard output using functions such as print()
(because this is a challenge problem, a naive solution will most likely have a Time Limit Exceeded result)
(this problem is an adaptation from a SWERC'2024 problem)
Naruto Uzumaki, the spirited ninja of the Hidden Leaf Village, has embarked on an unusual mission - helping archaeologists uncover the secrets of an ancient Japanese temple buried for centuries. The architecture of the temple is very curious: you found a line of \(N\) towers of different heights (no two towers have the same height), all spaced by one meter (the radius of each tower is supposed to be negligible).
During the excavations, you find something which might explain this curious architecture: the tomb of the architect. You find the following epitaph on the tomb:
O thou temple-builder,
To achieve perfection, visit each tower;
For each, compute the distance to the closest tower that is taller1;
Add every such distance.
If thou can follow this guidance,
Enlightened shalt thou be by this result,
And great in thy temple shall be the cult.
1(the closest taller tower can be on the left or on the right. For the tallest tower, this distance is undefined and should not be considered in the final sum)
You wonder how to compute this sum, this "enlightenment score" of the temple.
You are given a positive integer N corresponding to the number of towers, and an array \(H\) of \(N\) distinct non-negative integers corresponding to the heights of the towers. \(H_0\) is the height of the leftmost tower, \(H_1\) is the height of the tower to the right of \(H_0\), and so on. Finally, \(H_{N-1}\) is the height of the rightmost tower. Observe that the distance between any two towers, in meters, is the absolute value of the difference of their respective indices in the array \(H\). Let \(p\) denote the index of the tallest tower in \(H\) and define, for every \(i\neq p\),
\(d(i) = min\{|i ā j|: \text{for every } j \text{ such that } H_j > H_i\}\)
Note that \(d(p)\) is not defined. The "enlightenment score" of the temple is then given by \(\displaystyle\sum^{N-1}_{i=0, i \neq p} d(i)\)
Write a program that, given the number of towers \(N\) and the array of heights (\H\), computes the "enlightenment score".
The first line contains the integer \(N\). The second line contains the list of elements \(H_0, \ldots, H_{Nā1}\) of the array \(H\) of heights, separated by single spaces.
The output should contain one line with the enlightenment score of the temple.
The following limits are guaranteed in all the test cases that will be given to your program:
| \(2 \leq N \leq 200\,000\) | Number of towers | |
| \(0 \leq H_i \leq 10^{18}\) | Height of each tower |
| Example Input 1 | Example Output 1 |
5 7 3 2 100 1 |
6 |
Explanation of Sample Input 1
The tallest tower (the 4th) is not considered. Hence, 3+1+1+1=6.
| Example Input 2 | Example Output 2 |
8 45 13 18 10 8 56 17 19 |
13 |
Explanation of Sample Input 2
The tallest tower (the 6th) is not considered. Hence, 5+1+2+1+1+1+2=13.