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ên một dãy gồm n số nguyên dương c₁, c₂, …, c_n là mã của n vé. Vé thứ i (i = 1, 2, …, n) có mã là c_i.

Cặp vé (i, j) với 1 ≤ i < j ≤ n, sẽ trúng thưởng nếu trong hai mã của hai vé đó là c_i và c_j có một số bằng số lớn nhất, số còn lại sẽ bằng số nhỏ nhất trong các số c_i, c_i+1, …, c_j. Tức là khi đặt x = min(c_i, c_i+1, …, c_j), y = max(c_i, c_i+1, …, 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₁, c₂, …, 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 ≤ n ≤ 2×10⁵).
- Dòng 2 ghi n số nguyên dương c₁, c₂, …, c_n (1 ≤ c_i ≤ 10⁸, i = 1, 2, …, n).

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.

Ví dụ

TrungThuong.INP
5
3 3 1 6 5

TrungThuong.OUT
5

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

Cặp (i, j) c_i c_j  X = min(c_i..c_j) Y = max(c_i..c_j) Kết luận
    (1, 2) 3   3    3                 3                 c_i = x; c_j = y
    (2, 3) 3   1    1                 3                 c_i = y; c_j = x
    (3, 4) 1   6    1                 6                 c_i = x; c_j = y
    (5, 5) 6   5    5                 6                 c_i = y; c_j = x
    (1, 3) 2   1    1                 3                 c_i = y; c_j = x

Giới hạn

- 40% số test ứng với 40% số điểm thỏa mãn 2 ≤ n ≤ 200.
- 40% số test ứng với 40% số điểm thỏa mãn 200 ≤ n ≤ 2000.
- 20% số test ứng với 20% số điểm thỏa mãn 2000 < n ≤ 2×10⁵, 1 ≤ c_i ≤ 3.