<p>There are <code>n</code> soldiers standing in a line. Each soldier is assigned a <strong>unique</strong> <code>rating</code> value.</p>

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

<ul>
	<li>Choose 3 soldiers with index (<code>i</code>, <code>j</code>, <code>k</code>) with rating (<code>rating[i]</code>, <code>rating[j]</code>, <code>rating[k]</code>).</li>
	<li>A team is valid if: (<code>rating[i] &lt; rating[j] &lt; rating[k]</code>) or (<code>rating[i] &gt; rating[j] &gt; rating[k]</code>) where (<code>0 &lt;= i &lt; j &lt; k &lt; n</code>).</li>
</ul>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> rating = [2,5,3,4,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> rating = [2,1,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> We can&#39;t form any team given the conditions.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> rating = [1,2,3,4]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == rating.length</code></li>
	<li><code>3 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= rating[i] &lt;= 10<sup>5</sup></code></li>
	<li>All the integers in <code>rating</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    int solve(int i, int n, int cnt, bool increasing, vector<int>& rating, vector<vector<vector<int>>>& dp) {
        if (cnt == 3) {
            return 1;
        }
        if (i >= n) {
            return 0;
        }
        if (dp[i][cnt][increasing] != -1) {
            return dp[i][cnt][increasing];
        }
        
        int count =0;
        for (int j = i + 1; j < n; ++j) {
            if ((increasing && rating[j] > rating[i]) || (!increasing && rating[j] < rating[i])) {
                count += solve(j, n, cnt + 1, increasing, rating, dp);
            }
        }
        
        return dp[i][cnt][increasing] = count;
    }
    
    int numTeams(vector<int>& rating) {
        int n = rating.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(4, vector<int>(2, -1)));
        
        int total = 0;
        for (int i = 0; i < n; ++i) {
            total += solve(i, n, 1, true, rating, dp); // Increasing sequence
            total += solve(i, n, 1, false, rating, dp); // Decreasing sequence
        }
        
        return total;
    }
};


// class Solution {
// public:
//     int numTeams(vector<int>& rating) {
//         int n = rating.size();
//         int count = 0;

//         for (int i = 0; i < n; i++) {
//             int leftLess = 0, leftMore = 0;
//             int rightLess = 0, rightMore = 0;

//             // Count elements less than and greater than rating[i] on the left side
//             for (int j = 0; j < i; j++) {
//                 if (rating[j] < rating[i]) {
//                     leftLess++;
//                 } else if (rating[j] > rating[i]) {
//                     leftMore++;
//                 }
//             }

//             // Count elements less than and greater than rating[i] on the right side
//             for (int k = i + 1; k < n; k++) {
//                 if (rating[k] < rating[i]) {
//                     rightLess++;
//                 } else if (rating[k] > rating[i]) {
//                     rightMore++;
//                 }
//             }

//             // Calculate the number of valid teams with rating[i] as the middle element
//             count += leftLess * rightMore + leftMore * rightLess;
//         }

//         return count;
//     }
// };

17376