수열과 쿼리

길이가 $n$인 수열 $(s_1, s_2, \ldots, s_n)$이 주어진다. 함수 $f$는 다음과 같이 정의된다.

$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}$

다음 합의 값을 구하라.

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

첫 번째 줄에 수열의 길이를 나타내는 정수 $n$이 주어진다.

두 번째 줄에 $n$개의 정수 $s_1, s_2, \ldots, s_n$이 공백으로 구분되어 주어진다.

$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{\min(n-i+1,\, n-j+1)} f(i,j,k)$의 값을 출력한다.

• $1\leq n\leq 5\,000$
• $1\leq s_x\leq 10^9$ ($1\leq x\leq n$)

$i = j$인 경우 모든 $t$에 대해 $s_{i+t} \leq s_{i+t}$가 성립하므로 $f(i,i,k)$는 항상 1이다.