Queries, Queries Everywhere

For L…R, we have n = R - L + 1 nodes.

It is always optimal to connect all nodes to the node with the smallest value, or to connect the nodes in order of increasing value.

It will incur a cost of sum ( a[L], a[L+1], … a[R] ) - min( a[L], a[L+1], … a[R]).

Use any data structure that allows for point updates and range queries, i.e: segment tree.

Squeezing in sqrt structures may be possible with compiler black magic but it is not worth it.