# 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/fidai-biao-yiinput-i-wei-jie-wei-de-zhi/1395.-count-number-of-teams.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.