Cặp vé trúng thưởng

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, \dots, c_n$ là mã của $n$ vé. Vé thứ $i$ $(i = 1, 2, \dots, n)$ có mã là $c_i$. Cặp vé $(i, j)$ với $1 \le i < j \le 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}, \dots, c_j$. Tức là khi đặt $x = min(c_i, c_{i+1}, \dots, c_j)$; $y = max(c_i, c_{i+1}, \dots, 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, \dots, c_n$, hãy đưa ra số cặp vé trúng thưởng.

Dữ liệu cho trong tệp văn bản TrungThuong.Inp gồm:

• Dòng 1 ghi số nguyên dương $n$ $(2 \le n \le 2 \times 10^5)$.
• Dòng 2 ghi $n$ số nguyên dương $c_1, c_2, \dots, c_n$ $(1 \le c_i \le 10^8, i = 1, 2, \dots, n)$.

Các số ghi trên một dòng được phân cách nhau bởi dấu cách trống.

Kết quả ghi ra tệp văn bản TrungThuong.Out một số nguyên duy nhất là số cặp vé trúng thưởng.

• 40% số test ứng với 40% số điểm thỏa mãn $2 \le n \le 200$;
• 40% số test ứng với 40% số điểm thỏa mãn $200 < n \le 2000$;
• 20% số test ứng với 20% số điểm thỏa mãn $2000 < n \le 2 \times 10^5$; $1 \le c_i \le 3$; $i = 1, 2, \dots, n$.