310622: CF1861D. Sorting By Multiplication
Description
You are given an array $a$ of length $n$, consisting of positive integers.
You can perform the following operation on this array any number of times (possibly zero):
- choose three integers $l$, $r$ and $x$ such that $1 \le l \le r \le n$, and multiply every $a_i$ such that $l \le i \le r$ by $x$.
Note that you can choose any integer as $x$, it doesn't have to be positive.
You have to calculate the minimum number of operations to make the array $a$ sorted in strictly ascending order (i. e. the condition $a_1 < a_2 < \dots < a_n$ must be satisfied).
InputThe first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$.
The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.
Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
OutputFor each test case, print one integer — the minimum number of operations required to make $a$ sorted in strictly ascending order.
ExampleInput3 5 1 1 2 2 2 6 5 4 3 2 5 1 3 1 2 3Output
3 2 0Note
In the first test case, we can perform the operations as follows:
- $l = 2$, $r = 4$, $x = 3$;
- $l = 4$, $r = 4$, $x = 2$;
- $l = 5$, $r = 5$, $x = 10$.
In the second test case, we can perform one operation as follows:
- $l = 1$, $r = 4$, $x = -2$;
- $l = 6$, $r = 6$, $x = 1337$.
In the third test case, the array $a$ is already sorted.
Output
给定一个由正整数组成的长度为n的数组a。可以执行以下操作任意次数(可能为零):选择三个整数l、r和x,使得1≤l≤r≤n,并将每个满足l≤i≤r的ai乘以x。注意,可以选择任何整数作为x,它不一定是正数。需要计算使数组a按严格递增顺序排序所需的最小操作数(即满足条件a1 < a2 < ... < an)。
输入输出数据格式:
输入格式:
第一行包含一个整数t(1≤t≤10^4)——测试用例的数量。
每个测试用例的第一行包含一个整数n(1≤n≤2×10^5)——数组a的长度。
每个测试用例的第二行包含n个整数a1,a2,...,an(1≤ai≤10^9)——数组a。
输入附加限制:所有测试用例的n之和不超过2×10^5。
输出格式:
对于每个测试用例,打印一个整数——使a按严格递增顺序排序所需的最小操作数。题目大意: 给定一个由正整数组成的长度为n的数组a。可以执行以下操作任意次数(可能为零):选择三个整数l、r和x,使得1≤l≤r≤n,并将每个满足l≤i≤r的ai乘以x。注意,可以选择任何整数作为x,它不一定是正数。需要计算使数组a按严格递增顺序排序所需的最小操作数(即满足条件a1 < a2 < ... < an)。 输入输出数据格式: 输入格式: 第一行包含一个整数t(1≤t≤10^4)——测试用例的数量。 每个测试用例的第一行包含一个整数n(1≤n≤2×10^5)——数组a的长度。 每个测试用例的第二行包含n个整数a1,a2,...,an(1≤ai≤10^9)——数组a。 输入附加限制:所有测试用例的n之和不超过2×10^5。 输出格式: 对于每个测试用例,打印一个整数——使a按严格递增顺序排序所需的最小操作数。