2108C.md (3134B)
1 Source: https://codeforces.com/problemset/problem/2108/C 2 3 C. Neo's Escape 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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$. 22 23 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: 24 25 1. Create a clone in front of a specific button. 26 2. Move an existing clone one position to the left or right. 27 28 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. 29 30 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$. 31 32 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. 33 34 Input 35 36 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. 37 38 The first line of each test case contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of buttons. 39 40 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. 41 42 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 43 44 Output 45 46 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. 47 48 Example 49 50 Input 51 52 ``` 53 4 54 55 5 56 57 4 3 2 1 5 58 59 3 60 61 1 1 1 62 63 6 64 65 7 8 1 5 9 2 66 67 10 68 69 1 7 9 7 1 10 2 10 10 7 70 ``` 71 72 Output 73 74 ``` 75 2 76 1 77 2 78 3 79 ``` 80 81 Note 82 83 In the first test case, Neo can act as follows: 84 85 1. Create a clone in front of the fifth button (with weight $5$). 86 2. Create a clone in front of the first button (with weight $4$). 87 3. Move the second clone from the first button to the second (with weight $3$). 88 4. Move the second clone from the second button to the third (with weight $2$). 89 5. Move the first clone from the fifth button to the fourth (with weight $1$). 90 91 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. 92 93 In the second test case, Neo can act as follows: 94 95 1. Create a clone in front of the second button (with weight $1$). 96 2. Move the clone from the second button to the third (with weight $1$). 97 3. Move the clone from the third button to the second (already pressed). 98 4. Move the clone from the second button to the first (with weight $1$). 99 100 Thus, the sequence of button presses will be $1 \rightarrow 1 \rightarrow 1$.