Bộ ba tăng

Submit solution
Points: 4 (partial)
Time limit: 1.0s
Java 8 2.0s
Python 3 5.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

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


  • 0
    Ryze  commented on Sept. 3, 2024, 2:55 p.m.

    Cây BIT, dùng 2 vòng for cập nhật!


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

    6

    0 1 2 3 4 5

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


    • 1
      TICHPX  commented on Oct. 12, 2020, 10: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, 12:56 p.m.

        vâng haha e in ra min có 0


        • 2
          TICHPX  commented on Oct. 12, 2020, 1:07 p.m. ← edited

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


  • 1
    TICHPX  commented on May 3, 2020, 3:27 a.m.

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