Công ty xổ số BlueCode phát hành \(n\) vé số đặc biệt để chào mừng ngày thành lập. Các vé được đánh số thứ tự từ 1 đến \(n\). Hệ thống quay thưởng sẽ tạo ra ngẫu nhiêu một dãy gồm \(n\) số nguyên dương \(c_{1},c_{2},\ldots,c_{n}\) là mã của \(n\) vé. Vé thứ \(i\ (i = 1,\ 2,\ \ldots,\ n)\) có mã là \(c_{i}\). Cặp vé (\(i,\ j\)) với \(1 \leq i < j \leq n,\) sẽ trúng thưởng nếu trong hai mã của hai vé đó là \(c_{i}\) và \(c_{j}\) sẽ có một số bằng số lớn nhất, số còn lại bằng số nhỏ nhất trong các số \(c_{i},c_{i + 1},\ldots,c_{j}\). Tức là khi đặt \(x\ = \ min\left( c_{i},c_{i + 1},\ldots,c_{j} \right);y = max(c_{i},c_{i + 1},\ldots,c_{j})\) thì trong hai số \(c_{i}\) và \(c_{j}\) sẽ có một số bằng \(x\), số còn lại bằng \(y\). Công ty muốn biết có bao nhiêu cặp vé sẽ trúng thưởng nên đã nhờ bạn An lập trình để tính số cặp vé trúng thưởng.

Yêu cầu: Cho biết dãy gồm \(n\) số nguyên dương \(c_{1},c_{2},\ldots,c_{n}\), hãy đưa ra số cặp vé trúng thưởng.

Dữ liệu vào:

+ Dòng 1 ghi số nguyên dương \(n\) (2 \(\leq n \leq 2 \times 10^{5}\)).

+ Dòng 2 ghi \(n\) số nguyên dương \(c_{1},c_{2},\ldots,c_{n}\) (1 \(\leq c_{i} \leq 10^{8},\ i = 1,\ 2,\ldots,n)\).

Kết quả:

+ Ghi một số nguyên duy nhất là số cặp vé trúng thưởng.

Ví dụ:

Giải thích: Ta có 5 cặp vé trúng thưởng

Giới hạn:

+ 40% số test ứng với 40% số điểm thỏa mãn 2 \(\leq n \leq 200;\)

+ 40% số test ứng với 40% số điểm thỏa mãn 200 \(< n \leq 2000;\)

+ 20% số test ứng với 20% số điểm thỏa mãn 2000 \(< n \leq 2 \times 10^{5};1 \leq c_{i} \leq 3;i = 1,\ 2,...,n.\)