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] &lt; rating[j] &lt; rating[k]) or (rating[i] &gt; rating[j] &gt; rating[k]) where (0 &lt;= i &lt; j &lt; k &lt; n).


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

&nbsp;
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


&nbsp;
Constraints:


	n == rating.length
	3 &lt;= n &lt;= 1000
	1 &lt;= rating[i] &lt;= 105
	All the integers in rating are unique.


class Solution:
    def numTeams(self, ratings: List[int]) -> int:
        upper_dps = [0 for _ in range(len(ratings))]
        lower_dps = [0 for _ in range(len(ratings))]
        
        count = 0
        for i in range(len(ratings)):
            for j in range(i):
                if ratings[j] < ratings[i]:
                    count += upper_dps[j]
                    upper_dps[i] += 1
                else:
                    count += lower_dps[j]
                    lower_dps[i] += 1
                    
        return count
// Smaller * Larger Solution
// sum of #smaller * #larger
// Time complexity: O(N^2)
// Space complexity: O(1)
class Solution {
    public int numTeams(int[] rating) {
        final int N = rating.length;
        int res = 0;
        for (int i = 1; i < N; i++) {
            res += smaller(rating, i, -1) * larger(rating, i, 1);
            res += larger(rating, i, -1) * smaller(rating, i, 1);
        }
        return res;
    }
    
    private int smaller(int[] rating, int i, int diff) {
        int t = rating[i], count = 0;
        i += diff;
        while (i >= 0 && i < rating.length) {
            if (rating[i] < t) count++;
            i += diff;
        }
        return count;
    }
    
    private int larger(int[] rating, int i, int diff) {
        int t = rating[i], count = 0;
        i += diff;
        while (i >= 0 && i < rating.length) {
            if (rating[i] > t) count++;
            i += diff;
        }
        return count;
    }
}
class Solution {
public:
    int numTeams(vector<int>& rating) {

        int i, j, n = rating.size(), ans = 0;
        vector<int> grt(n, 0), les(n, 0);
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(rating[j] > rating[i])
                    grt[i] += 1;
                else
                    les[i] += 1;
            }
        }

        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(rating[j] > rating[i])
                    ans += grt[j];
                else
                    ans += les[j];
            }
        }
        return ans;
    }
};
// counting bigger / smaller elements
// if after rating[i] has X bigger elements,
// and each element has Y bigger elements after them
// hence total elements that has i < j < k and rating[i] < rating[j] < rating[k]
// same for the number of smaller elements
// so the key point here is to know how many elements
// that smaller and bigger than the current number
var numTeams = function(rating) {
    // save total number of elements after i
    // that smaller than rating[i]
    let big = new Array(rating.length).fill(0)

    let n = rating.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            if (rating[j] > rating[i]) big[i]++;
        }
    }

    let count = 0;
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            if (rating[j] > rating[i]) count += big[j]

            // because all elements are unique, so
            // we don't need to calculate the number of smaller elements
            // because if there are X bigger elements after rating[i]
            // then there are (n - i - 1 - X) smaller elements after rating[i]
            // or small = n - i - 1 - big
            else count += n - j - 1 - big[j];
        }
    }

    return count;
}
Count Number of Teams