Count Triplets with Sum Less than a Given Value

You are given an array of integers and a target sum S. Your task is to count the number of triplets (i, j, k) such that 0 ≤ i < j < k < n and the sum of the triplet is less than S. In other words, you need to find the number of triplets such that:

[ a_i + a_j + a_k < S ]

The array may contain duplicate elements. The counting should consider each triplet only once, and the order of indices must be maintained (i < j < k).

Example:

• For arr = [5, 1, 3, 4, 7] and S = 12, the triplets that satisfy the condition are (5, 1, 3), (5, 1, 4), (5, 3, 4), and (1, 3, 4). Thus, the answer is 4.

inputFormat

The input consists of three lines:

1. The first line contains an integer n denoting the number of elements in the array.
2. The second line contains n space-separated integers representing the array.
3. The third line contains an integer S representing the sum threshold.

You can assume that n ≥ 3.

outputFormat

Output a single integer that denotes the number of triplets (i, j, k) such that a[i] + a[j] + a[k] < S.

## sample

5
5 1 3 4 7
12

4

</p>