CF2108C Neo's Escape

Neo wants to escape from the Matrix. In front of him are $ n $ buttons arranged in a row. Each button has a weight given by an integer: $ a_1, a_2, \ldots, a_n $ . Neo is immobilized, but he can create and move clones. This means he can perform an unlimited number of actions of the following two types in any order: 1. Create a clone in front of a specific button. 2. Move an existing clone one position to the left or right. As soon as a clone is in front of another button that has not yet been pressed—regardless of whether he was created or moved — he immediately presses it. If the button has already been pressed, a clone does nothing — buttons can only be pressed once. For Neo to escape, he needs to press all the buttons in such an order that the sequence of their weights is non-increasing — that is, if $ b_1, b_2, \ldots, b_n $ are the weights of the buttons in the order they are pressed, then it must hold that $ b_1 \geq b_2 \geq \cdots \geq b_n $ . Your task is to determine the minimum number of clones that Neo needs to create in order to press all the buttons in a valid order.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the number of buttons. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the weights of the buttons. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output one integer — the minimum number of clones that need to be created to press all the buttons in a valid order.

In the first test case, Neo can act as follows: 1. Create a clone in front of the fifth button (with weight $ 5 $ ). 2. Create a clone in front of the first button (with weight $ 4 $ ). 3. Move the second clone from the first button to the second (with weight $ 3 $ ). 4. Move the second clone from the second button to the third (with weight $ 2 $ ). 5. Move the first clone from the fifth button to the fourth (with weight $ 1 $ ). Thus, the sequence of button presses will be $ 5 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 1 $ , which meets the requirement. It can be shown that the number of clones created is the smallest possible.In the second test case, Neo can act as follows: 1. Create a clone in front of the second button (with weight $ 1 $ ). 2. Move the clone from the second button to the third (with weight $ 1 $ ). 3. Move the clone from the third button to the second (already pressed). 4. Move the clone from the second button to the first (with weight $ 1 $ ). Thus, the sequence of button presses will be $ 1 \rightarrow 1 \rightarrow 1 $ .