Ignoring TLE,let's calculate $$$f(s)$$$ at first.I'd like to transform the problem into this:divide the sequence into some segments whose length is more than 2,each segment's cost is the first number times the length -1.For example,2 2 2,it's cost is 4.Set $$$f_{i,j}$$$ means,explore first i elements,the first number of the last segment is j.It's easy to calculate now.

Means that,I can append $$$i_{th}$$$ number just in the back of the last segment,or make a new segment with $$$a_{i-1}$$$.

It costs $$$O(n)$$$ for each query,and got TLE.We can use ddp.Use matrix to draw the dp.Especially,the $$$\times$$$ means add.the $$$+$$$ means $$$\min$$$.Let $$$\min_i=\min_1^9 f_{i,j}$$$,we can design the vector as follows:

I'd like to show you $$$i_{th}$$$ matrix with $$$a_{i-1}=2$$$("i" means inf):

It's easy to use segment tree to solve this,but might TLE.Just use blocks,since the len of each query is const.

Also,I'm working on how to get the inverse of the matrix.Guass might work.

code