Đếm cặp

View as PDF
Submit solution
Points: 0.33 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

~N~ người đang đứng xếp hàng chờ mua vé vào buổi hòa nhạc. Mọi người đều phát chán khi phải chờ đợi, vì vậy họ nhìn quanh xem có ai quen hay không.

Hai người ~A~ và ~B~ đứng trong hàng có thể nhìn thấy nhau nếu:

  • Người ~A~ và người ~B~ đang đứng cạnh nhau.
  • Giữa người ~A~ và người ~B~, không có ai cao hơn hẳn một trong hai người.

Hãy đếm xem có bao nhiêu cặp có thể nhìn thấy nhau trong hàng.

Input

  • Dòng đầu tiên chứa số nguyên dương ~N~, là số người đang đứng trong hàng.
  • Mỗi dòng trong ~N~ dòng tiếp theo chứa một số nguyên là chiều cao của một người tính bằng nanomet. (Tất cả mọi người đều thấp hơn ~2^{31}~ nanomet).

Output

  • Một số nguyên duy nhất là kết quả cần tìm.

Giới hạn

  • ~1 \leq N \leq 5\times 10^{5}~
  • Trong ~\frac{1}{3}~ số test ~1 \leq N \leq 5000~

Sample Input

7
2
4
1
2
2
5
1

Sample Output

10

Note

Các cặp có thể nhìn thấy nhau là ~(1, 2), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (4, 5), (4, 6), (5, 6), (6, 7)~.

Comments

Please read the guidelines before commenting.


  • 1
    10Tin_Phan_Ba_Kha  commented on Sept. 9, 2024, 7:57 a.m.

    HILLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLer


  • -20
    chunguyen2k8  commented on May 13, 2024, 9:05 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 103
    kienoniichan123  commented on Oct. 23, 2022, 8:44 a.m.

    hilu


  • -24
    tphatdzai  commented on June 5, 2022, 9:01 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -49
    duyanh  commented on April 14, 2022, 2:49 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.