Bộ ba tăng


Submit solution

Points: 4 (partial)
Time limit: 1.0s
Java 8 2.0s
Memory limit: 98M

Author:
Problem type

Bài toán nhập vào dãy số nguyên \(a_1,a_2,...a_n\) đếm tất cả các bộ 3 số tăng dần trong dãy. Tức là đếm số bộ \((a_i,a_j,a_k)\) với \(1 \le i < j < k \le n\) mà \(a_i <a_j < a_k\)

Input

Dòng đầu chứa số nguyên dương n là cỡ của phép thế \((1 <= n<= 10^5)\)

Dòng thứ 2 gồm n số tự nhiên có giá trị không vượt quá \(10^5\)

Output

Một số nguyên dương duy nhất là số bộ ba tăng của dãy.

Ví dụ

Input

9
4 7 2 8 4 8 3 1 2

Output

3

Giải thích: có 3 bộ ba phần tử tăng ngặt là \((a_1,a_2,a_4); (a_1,a_2,a_6); (a_3,a_5,a_6)\)

tichpx

Comments


  • 1
    enoughtodie99  commented on Oct. 11, 2020, 11:15 a.m.

    6

    0 1 2 3 4 5

    thì ra bao nhiêu thầy nhỉ


    • 1
      TICHPX  commented on Oct. 12, 2020, 6:22 a.m.

      Chắc phải 20, mình làm đề cho số nguyên dương mà test lại có số 0 nên sai test chắc mình phải sửa lại


      • 1
        enoughtodie99  commented on Oct. 12, 2020, 8:56 a.m.

        vâng haha e in ra min có 0


        • 2
          TICHPX  commented on Oct. 12, 2020, 9:07 a.m. edited

          OK, I've already updated test data for this problem


  • 1
    TICHPX  commented on May 2, 2020, 11:27 p.m.

    Bài này dùng cây IT