# 1395. Count Number of Teams

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`

找数组中长度为3的递增序列和递减序列的总数。increasing subseq => DP。当遍历到i时，nums\[i]会作为序列尾（第三个元素），需要对前面的j的已有结果，也就是序列长度为2的，做遍历，因此dp\[j]存以nums\[j]为递增（减）序列第二个位置时序列的个数。i每次能和前面j拼在一起时，res += dp\[j]。

```python
class Solution:
    def numTeams(self, rating: List[int]) -> int:
        n = len(rating)
        dp_g, dp_l = [0] * n, [0] * n
        res = 0
        for i, r in enumerate(rating):
            for j in range(i):
                if r > rating[j]:
                    dp_g[i] += 1
                    res += dp_g[j]
                elif r < rating[j]:
                    dp_l[i] += 1
                    res += dp_l[j]
        return res
```