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:
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.
454 3 2 1 531 1 167 8 1 5 9 2101 7 9 7 1 10 2 10 10 7
2 1 2 3
In the first test case, Neo can act as follows:
In the second test case, Neo can act as follows: