// logic for counting triplets in an array where the middle element is smaller than both the other two elements
// Implemented in Python for clarity
// just count the greater elem on left and right for each middle element
/* 
    for j in range(1, n - 1):  # j is the middle element
        count_greater_left = 0
        count_greater_right = 0
 
        # Count elements greater than arr[j] on the left
        for i in range(j):
            if arr[i] > arr[j]:
                count_greater_left += 1
 
        # Count elements greater than arr[j] on the right
        for k in range(j + 1, n):
            if arr[k] > arr[j]:
                count_greater_right += 1
 
        # Update triplet count
        triplet_count += count_greater_left * count_greater_right
 
    return triplet_count
 
# Example usage
arr = [5, 3, 4, 2, 1]
print(count_triplets(arr))  # Output: Number of valid triplets
*/
 
import java.util.*;
class TripletCounter {
 
    public static int countTriplets(int[] arr) {
        int n = arr.length;
        int tripletCount = 0;
 
        // Iterate through each element as the middle element
        for (int j = 1; j < n - 1; j++) {
            int countGreaterLeft = 0;
            int countGreaterRight = 0;
 
            // Count elements greater than arr[j] on the left
            for (int i = 0; i < j; i++) {
                if (arr[i] > arr[j]) {
                    countGreaterLeft++;
                }
            }
 
            // Count elements greater than arr[j] on the right
            for (int k = j + 1; k < n; k++) {
                if (arr[k] > arr[j]) {
                    countGreaterRight++;
                }
            }
 
            // Update triplet count
            tripletCount += countGreaterLeft * countGreaterRight;
        }
 
        return tripletCount;
    }
 
    public static void main(String[] args) {
        int[] arr = {5, 3, 4, 2, 1};
        int result = countTriplets(arr);
        System.out.println("Number of valid triplets: " + result);
    }
}
 

Ly8gbG9naWMgZm9yIGNvdW50aW5nIHRyaXBsZXRzIGluIGFuIGFycmF5IHdoZXJlIHRoZSBtaWRkbGUgZWxlbWVudCBpcyBzbWFsbGVyIHRoYW4gYm90aCB0aGUgb3RoZXIgdHdvIGVsZW1lbnRzCi8vIEltcGxlbWVudGVkIGluIFB5dGhvbiBmb3IgY2xhcml0eQovLyBqdXN0IGNvdW50IHRoZSBncmVhdGVyIGVsZW0gb24gbGVmdCBhbmQgcmlnaHQgZm9yIGVhY2ggbWlkZGxlIGVsZW1lbnQKLyogCiAgICBmb3IgaiBpbiByYW5nZSgxLCBuIC0gMSk6ICAjIGogaXMgdGhlIG1pZGRsZSBlbGVtZW50CiAgICAgICAgY291bnRfZ3JlYXRlcl9sZWZ0ID0gMAogICAgICAgIGNvdW50X2dyZWF0ZXJfcmlnaHQgPSAwCgogICAgICAgICMgQ291bnQgZWxlbWVudHMgZ3JlYXRlciB0aGFuIGFycltqXSBvbiB0aGUgbGVmdAogICAgICAgIGZvciBpIGluIHJhbmdlKGopOgogICAgICAgICAgICBpZiBhcnJbaV0gPiBhcnJbal06CiAgICAgICAgICAgICAgICBjb3VudF9ncmVhdGVyX2xlZnQgKz0gMQoKICAgICAgICAjIENvdW50IGVsZW1lbnRzIGdyZWF0ZXIgdGhhbiBhcnJbal0gb24gdGhlIHJpZ2h0CiAgICAgICAgZm9yIGsgaW4gcmFuZ2UoaiArIDEsIG4pOgogICAgICAgICAgICBpZiBhcnJba10gPiBhcnJbal06CiAgICAgICAgICAgICAgICBjb3VudF9ncmVhdGVyX3JpZ2h0ICs9IDEKCiAgICAgICAgIyBVcGRhdGUgdHJpcGxldCBjb3VudAogICAgICAgIHRyaXBsZXRfY291bnQgKz0gY291bnRfZ3JlYXRlcl9sZWZ0ICogY291bnRfZ3JlYXRlcl9yaWdodAoKICAgIHJldHVybiB0cmlwbGV0X2NvdW50CgojIEV4YW1wbGUgdXNhZ2UKYXJyID0gWzUsIDMsIDQsIDIsIDFdCnByaW50KGNvdW50X3RyaXBsZXRzKGFycikpICAjIE91dHB1dDogTnVtYmVyIG9mIHZhbGlkIHRyaXBsZXRzCiovCgppbXBvcnQgamF2YS51dGlsLio7CmNsYXNzIFRyaXBsZXRDb3VudGVyIHsKICAgIAogICAgcHVibGljIHN0YXRpYyBpbnQgY291bnRUcmlwbGV0cyhpbnRbXSBhcnIpIHsKICAgICAgICBpbnQgbiA9IGFyci5sZW5ndGg7CiAgICAgICAgaW50IHRyaXBsZXRDb3VudCA9IDA7CgogICAgICAgIC8vIEl0ZXJhdGUgdGhyb3VnaCBlYWNoIGVsZW1lbnQgYXMgdGhlIG1pZGRsZSBlbGVtZW50CiAgICAgICAgZm9yIChpbnQgaiA9IDE7IGogPCBuIC0gMTsgaisrKSB7CiAgICAgICAgICAgIGludCBjb3VudEdyZWF0ZXJMZWZ0ID0gMDsKICAgICAgICAgICAgaW50IGNvdW50R3JlYXRlclJpZ2h0ID0gMDsKCiAgICAgICAgICAgIC8vIENvdW50IGVsZW1lbnRzIGdyZWF0ZXIgdGhhbiBhcnJbal0gb24gdGhlIGxlZnQKICAgICAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBqOyBpKyspIHsKICAgICAgICAgICAgICAgIGlmIChhcnJbaV0gPiBhcnJbal0pIHsKICAgICAgICAgICAgICAgICAgICBjb3VudEdyZWF0ZXJMZWZ0Kys7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIC8vIENvdW50IGVsZW1lbnRzIGdyZWF0ZXIgdGhhbiBhcnJbal0gb24gdGhlIHJpZ2h0CiAgICAgICAgICAgIGZvciAoaW50IGsgPSBqICsgMTsgayA8IG47IGsrKykgewogICAgICAgICAgICAgICAgaWYgKGFycltrXSA+IGFycltqXSkgewogICAgICAgICAgICAgICAgICAgIGNvdW50R3JlYXRlclJpZ2h0Kys7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIC8vIFVwZGF0ZSB0cmlwbGV0IGNvdW50CiAgICAgICAgICAgIHRyaXBsZXRDb3VudCArPSBjb3VudEdyZWF0ZXJMZWZ0ICogY291bnRHcmVhdGVyUmlnaHQ7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gdHJpcGxldENvdW50OwogICAgfQoKICAgIHB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHsKICAgICAgICBpbnRbXSBhcnIgPSB7NSwgMywgNCwgMiwgMX07CiAgICAgICAgaW50IHJlc3VsdCA9IGNvdW50VHJpcGxldHMoYXJyKTsKICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oIk51bWJlciBvZiB2YWxpZCB0cmlwbGV0czogIiArIHJlc3VsdCk7CiAgICB9Cn0K