Sequence and Queries

Interview

Time limit1sMemory limit1024 MB

Summary

Count triples (i, j, k) where the length-k runs starting at positions i and j satisfy s[i+t] <= s[j+t] for every offset t below k.

Problem

A sequence $(s_1, s_2, \ldots, s_n)$ of length $n$ is given. The function $f$ is defined as follows.

$f(i,j,k) = \begin{cases} 1 & \text{if } s_{i+t} \leq s_{j+t} \text{ for all } 0 \leq t < k \\ 0 & \text{otherwise} \end{cases}$

Print the value of the following sum.

$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{\min(n-i+1,\, n-j+1)} f(i,j,k)$

The first line contains the integer $n$ , the length of the sequence.

The second line contains $n$ integers $s_1, s_2, \ldots, s_n$ , separated by spaces.

Print the value of $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{\min(n-i+1,\, n-j+1)} f(i,j,k)$ .

When $i = j$ , the inequality $s_{i+t} \leq s_{i+t}$ holds for every $t$ , so $f(i,i,k)$ is always 1.