같은 최댓값

Sasha는 프로그래밍 대회를 준비하면서 자료 구조와 관련 문제를 공부하고 있다. 그가 자주 본 문제 중 하나는 구간 최댓값 쿼리(Range Maximum Query)이다.

그 문제는 다음과 같이 정의된다. $n$개의 정수로 이루어진 배열 $a$가 있다: $a_1, a_2, \ldots, a_n$. "$i$번째 원소부터 $j$번째 원소까지의 구간에서 최댓값을 구하라"는 쿼리에 답해야 하므로, 계산할 값은 $\max \{a_i, a_{i+1}, \ldots, a_j\}$이다.

물론 Sasha에게 이 문제는 어렵지 않았고, 곧 이런 쿼리에 답하는 매우 빠른 프로그램을 만들었다. 답을 보던 그는 서로 다른 쿼리의 답이 자주 같다는 것을 알아차렸다.

이제 Sasha는 최댓값이 같은 두 개의 겹치지 않는 구간을 고르는 방법이 몇 가지인지 궁금해졌다.

여러분의 임무는 Sasha를 돕는 것이다. $1 \le i \le j < k \le l \le n$이고 $\max\{a_i, a_{i+1}, \ldots, a_j\} = \max\{a_k, a_{k+1}, \ldots, a_l\}$인 네 정수 $i$, $j$, $k$, $l$의 개수를 구하라. 그 수는 매우 클 수 있으므로 $1\,000\,000\,007$로 나눈 나머지를 출력해야 한다.

첫째 줄에 Sasha의 배열 길이 $n$이 주어진다 ($2 \le n \le 100\,000$). 둘째 줄에 배열의 원소 $n$개가 주어진다. 원소는 양수이며 $10^9$를 넘지 않는다.

최댓값이 같은 겹치지 않는 구간 쌍의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.

첫 번째 예제의 구간 쌍: