In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 20th
(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)
Steve, Robin, and Nancy discover that Vecna has been constructing a series of structures of different shapes in the Upside Down, all aligned in a long, unnerving formation, almost as if channeling power toward something hidden deeper in the other side. They form a line of \(N\) towers of different heights (no two towers have the same height), all spaced by one meter.
Each individual tower’s dark resonance, a value that indicates how strongly a tower gathers power, depends on the distance to the closest tower that is taller (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). The three friends need to compute the sum of all these individual values, to understand how much energy is Vecna planning to gather.
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 "total dark resonance" 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 "the total dark resonance".
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 total dark resonance of the structures.
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.