There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

Choose 3 soldiers with index (i, j, k) with rating (rating[i], rating[j], rating[k]).

A team is valid if: (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]

Output: 3

Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).

Example 2:

Input: rating = [2,1,3]

Output: 0

Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]

Output: 4

Constraints:

n == rating.length

1 <= n <= 200

1 <= rating[i] <= 10^5

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | int numTeams(int* rating, int ratingSize){ int sum = 0; for(int mid = 1; mid<ratingSize-1; ++mid){ int leftSmall = 0, leftGreat = 0; int rightSmall = 0, rightGreat = 0; for(int i = 0; i<ratingSize; ++i){ if(i==mid){ continue; } if(i<mid){ if(rating[i]<rating[mid]){ ++leftSmall; } else if(rating[i]>rating[mid]){ ++leftGreat; } } else{ if(rating[i]<rating[mid]){ ++rightSmall; } else if(rating[i]>rating[mid]){ ++rightGreat; } } } sum += leftSmall*rightGreat + leftGreat*rightSmall; } return sum; } |