Sequence and Queries

길이가 $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\le s\_x\le 10^9$ ($1\le x\le n$)

첫 번째 예제에 대한 설명은 다음과 같다.

• $f(1,1,1) =1$
• $f(1,1,2) =1$
• $f(1,2,1) =1$
• $f(2,1,1) =0$
• $f(2,2,1) =1$