Let’s first compute suffix array of the string and the height array \((h_i=LCP(suf_{sa_i},suf_{sa_{i-1}}))\). Here \(sa\) is the suffix array (index starts from 1), \(suf\) is the suffix of the string, \(LCP\) is longest common prefix. Let \(rnk_{sa_i}=i\).

There is a well-known conclusion that \(LCP(suf_i,suf_j)(rnk_i<rnk_j)\) is the minimum of \(h_{rnk_{i+1}},h_{rnk_{i+2}},\dots,h_{rnk_j}\),

By considering the suffixes in the order of \(rnk\), we can rewrite the problem to:

Given \(n\) integers \(a_1\sim a_n\), for every \(i\) compute \(\sum_{j=1}^n \min_{k=\min(i,j)}^{\max(i,j)} a_k\).

This can be solved easily with a stack in linear time.

The total time complexity is \(O(n+SA(n))\), where \(SA(n)\) is the time complexity you use to compute suffix arrays.