가시성

정수로 이루어진 수열 $x_1, x_2, \dots, x_n$이 주어진다.

두 원소 $x_i$와 $x_j$ ($1 \le i < j \le n$)가 서로 직접 보인다는 것은, 두 원소 사이에 있는 모든 원소 $x_{i+1}, \dots, x_{j-1}$이 $\min(x_i, x_j)$보다 작다는 뜻이다. 특히 이웃한 두 원소는 사이에 다른 원소가 없으므로 항상 서로 직접 보인다.

두 원소 $x_i$와 $x_j$ ($1 \le i < j \le n$)가 서로 간접적으로 보인다는 것은 다음 두 조건 중 하나가 성립한다는 뜻이다.

• 두 원소가 서로 직접 보이거나,
• $i < k < j$인 어떤 $k$가 존재하여 $x_i$와 $x_k$가 서로 직접 보이고, 동시에 $x_k$와 $x_j$도 서로 직접 보인다.

$1 \le i < j \le n$이면서 $x_i$와 $x_j$가 서로 간접적으로 보이는 쌍 $(i, j)$의 개수를 구하여라.

첫째 줄에 정수 $n$ ($1 \le n \le 40\,000$)이 주어진다. 이어지는 $n$개의 줄에는 수열의 원소가 순서대로 한 줄에 하나씩 주어지며, 각 원소는 $-1\,000\,000$ 이상 $1\,000\,000$ 이하의 정수이다.

$1 \le i < j \le n$이면서 $x_i$와 $x_j$가 서로 간접적으로 보이는 쌍 $(i, j)$의 개수를 한 줄에 출력한다.