Дано перестановку \(P\) для \(\{1, 2, \ldots, N\}\).

Для пари (\(L, R\)) (\(1 \le L \lt R \le N\)), нехай \(X_{L, R}\) буде другим за величиною значенням серед \(P_L, P_{L+1}, \ldots, P_R\).

Знайти \(\displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}\)

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число \(N\) (\(2 \le N \le 10^5\)).

Другий рядок містить \(N\) цілих чисел \(P_i\) (\(1 \le P_i \le N\), \(P_i \neq P_j\) при \(i \neq j\)), які розділяються пропуском.

Формат вихідних даних

У вихідний потік вивести шукану суму.

Примітка

До прикладу 1:

\(X_{1,2}=2\), \(X_{1,3}=2\), і \(X_{2, 3} = 1\), отже сума дорівнює 2 + 2 + 1 = 5.

Приклад вхідних даних

3
2 3 1

Приклад вихідних даних

5

Приклад вхідних даних

5
1 2 3 4 5

Приклад вихідних даних

30

Приклад вхідних даних

8
8 2 7 3 4 5 6 1

Приклад вихідних даних

136