Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Dancing Tuples

By Aashiq · Limits 3s, 512 MB

Given an array AA of size nn, find how many tuple (i,j,k)(i, j, k) are there such that
1i<j<kn1 ≤ i < j < k ≤ n and AjAiAkA_j ≤ A_i ≤ A_k.

Input

The first line contains an integer nn which represents the length of the array. The second line contains a sequence of n integers AiA_i.

1n1061≤n≤10^{6}
1Ain1 ≤ A_i ≤ n

Output

Print one integer — the number of valid tuples.

Samples

InputOutput
5
4 1 3 5 2 
2
InputOutput
6
2 5 3 2 5 6 
9
InputOutput
5
1 2 3 4 5 
0

    Discussion

    Statistics


    100% Solution Ratio

    riyad000Earliest, 1d ago

    riyad000Fastest, 0.4s

    riyad000Lightest, 48 MB

    riyad000Shortest, 4037B

    Submit

    Login to submit