Let's assume that we are at point $$$p$$$ now. We have two options.

1) Go to $$$t$$$ directly, paying extra $$$|p - t| * a_p$$$ money;

2) Go to another "optimal" point. There are two choices for that. Either it is minimum $$$r$$$ such that $$$a_r \lt a_p$$$ and $$$r \gt p$$$, or maximum $$$l$$$ such that $$$a_l \lt a_p$$$ and $$$l \lt p$$$.

So run Dijkstra, maintaining minimum distance. Update answer by the first option. Or go to the next optimal point paying $$$a_v * dist$$$ ($$$r - p$$$ or $$$p - l$$$) money. We are multiplying $$$a_v$$$ because each time we are going to the index with a lower value.

If I'm not wrong, it can also be solved by the Convex hull trick. The naive solution will be using DP. Let's say $$$dp_i$$$ is the minimum time needed to reach the point $$$i$$$. Recurrent relation will look like $$$dp_i = dp_j + |i - j| \cdot a_j$$$. It is easy to notice that the next point's value will be always less than the current's (i.e $$$a_{cur} \gt a_{next}$$$). So the $$$a's$$$ will be decreasing.

To solve in n^2logn, we can notice that actually if we reassing our element from L to R, their id to from 1 to R — L + 1, it is easy to notice that actually after each separation their indexes goes left shift. So having M different groups, we can answer the sum with the formula. Then we can notice that 1 to R — L + 1, does not matter and we can just add their initial ID. So with that we can do MO in Nsqrt(N)log(N), but it will also be TL. Then we can notice that it is enough to keep the last Position where such division starts, so just by fixing R we can answer L easily with that information. My realization was with Trie and Fenwich. Nlog^2

not today

Yes. To meme and author

Unofficial results already published.

yes

somehow, i had "ai = i; bi = i + 1" from the start of the contest, or i accidentally reloaded statements. im not sure

Or, at least, what it was (roughly) in the past years?

Put your code in a spoiler, please.

Explain your idea

Nice code, everyone in Novosibirsk writes so beautifully?

It should be. Editorial is likely to be published on IZhO like previous years.

Editorial is published.

Added

You can think of the problem as we start at position x and we want to always go to the left (and exit at door 1) we can create segment for each i where L = i + 1 and R is equal to what rooms is it optimal to visit on the right before visiting room i (supposing room i + 1 is the starting room) then using these segment for each i we can simply binary search to find the rightmost position j j <= i such that we would've already used the values in the range [i, n — 1] (i.e. left the array through the right door) trying to unlock the values [j,i]