Given an array of n distinct integers, and an integer threshold, how many (a,b,c) index triplets exist that satisfy both of the following conditions?

arr[a] < arr[b] < arr[c]

arr[a] + arr[b] + arr[c] <= t

Relevant Citadel OA Problems:

Triplets

Ways to Sum

Consecutive Sum

Disk Space Analysis

Do They Belong?

Global Maximum

Initial Public Offering

Inversions

Portfolio Balances

Prime Factor Visitation

Profit Targets

Sprint Training

Throttling Gateway

Birthday Card Collection

Parameter

arr: an array of integers

t: an integer threshold

Result

An integer that denotes the number of (a,b,c) triplets that satisfy the given conditions.

Example

Input: arr = [1, 2, 3, 4, 5], t = 8

The following 4 triplets satisfy the constraints: (1,2,3), (1,2,4), (1,2,5), (1,3,4).

Output: 4