408176: GYM103037 G Scale Goodness

As an avid musician, Santiago loves to practice his music and work on his fundamentals. One of his favorite exercises is playing through arbitrary scales with notes labelled from $$$1$$$ to $$$n$$$ in order. However, he's recently gotten tired of just playing the same scales over and over again and wants to switch up the order of the notes of the scale.

Before playing each note in the permuted scale, Santiago finds the highest previously played note lower than the current note, $$$l$$$, and the lowest previously played note higher than the current note, $$$r$$$, and defines the goodness of the note as the number of notes in the interval $$$(l, r)$$$ (exclusive). If no such $$$l$$$ exists, Santiago takes all notes equal to or below the current note as part of the interval and if no such $$$r$$$ exists, Santiago takes all notes equal to or above the current note as part of the interval.

Santiago then defines the total goodness of the scale ordering to be the sum of the goodness of the notes played within the scale ordering. Santiago feels he gets higher quality practice from scales with higher goodness. Given a proposed scale ordering, output the total goodness of the corresponding scale so that Santiago knows which scale orderings are worth practicing.

The input will consist of a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) giving the total number of notes in Santiago's scale. The next line consists of permutation of size $$$n$$$, $$$a_i$$$ $$$(1 \leq a_i \leq n)$$$, which represents that the $$$i$$$th note in the scale ordering is $$$a_i$$$.

Output the total goodness of the scale ordering as defined above.

5
3 4 5 2 1

11

The first note played, $$$3$$$, has a goodness of $$$5$$$ as no other notes have been played so all are included in the interval. The second note played, $$$4$$$, has a goodness of $$$2$$$ from the interval $$$(3, 5]$$$. The third note played, $$$5$$$, has a goodness of $$$1$$$ from the interval $$$(4, 5]$$$. The fourth note played, $$$2$$$, has a goodness of $$$2$$$ from the interval $$$[1, 3)$$$. The fifth note played, $$$1$$$, has a goodness of $$$1$$$ from the interval $$$[1, 2)$$$. Summing the goodness of each note gives us a total goodness of $$$5 + 2 + 1 + 2 + 1 = 11$$$.