oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

singlefile Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

singlefile.html

Problem Description

After successfully assigning his N participants to groups and completing the activity, Damian now has them back in single file.

Of course, each student has his/her own height Hi, making the line lack uniformity and thus look rather messy.

Damian wants to quantify just how messy the line is. Thus, he wants to know how many triplets of students i, j, k exist, where i < j < k in the line and Hi > Hj > Hk.

Input

The first line contains one integer, N, the number of participants.

The second line contains N space-separated integers, with the ith integer representing the height of the ith participant.

Output

The output should contain one line containing one integer, the number of such triplets.

Limits

For all subtasks, 1 ≤ Hi ≤ 109.

Subtask 1 (19%): 1 ≤ N ≤ 500.

Subtask 2 (35%): 1 ≤ N ≤ 10 000.

Subtask 3 (46%): 1 ≤ N ≤ 106.

Subtask 4 (0%): Sample Testcases.

Sample Testcase 1

Input

5
9 3 7 4 1

Output

5

Sample Testcase 1 Explanation

The triplets are {9, 3, 1}, {9, 7, 4}, {9, 7, 1}, {9, 4, 1} and {7, 4, 1}.

Tags

Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
119111s256MBMinimum
235211s256MBMinimum
346311s256MBMinimum
4011s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o singlefile -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.