← 返回题目列表

Codeforces · 2081/B

B. 平衡

中文机器翻译题面 查看原题

Ecrade 有一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。保证对于每个$$$1 \le i \lt n$$$,$$$a_i \neq a_{i+1}$$$。

Ecrade 可以对数组执行多项操作以使其严格递增。

在每个操作中,他可以选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 并将 $$$a_l, a_{l+1}, \ldots, a_r$$$ 替换为任何 $$$r-l+1$$$ 整数 $$$a'_l, a'_{l+1}, \ldots,a'_r$$$ 满足以下约束:

  • 对于每个 $$$l \le i \lt r$$$,$$$a'_i$$$ 和 $$$a'_{i+1}$$$ 之间的比较与 $$$a_i$$$ 和 $$$a_{i+1}$$$ 之间的比较相同,即如果 $$$a_i \lt a_{i + 1}$$$,则$$$a'_i \lt a'_{i + 1}$$$;否则,如果 $$$a_i \gt a_{i + 1}$$$,则 $$$a'_i \gt a'_{i + 1}$$$;否则,如果 $$$a_i = a_{i + 1}$$$,则 $$$a'_i = a'_{i + 1}$$$。

Ecrade 想知道使数组严格递增的最少操作数。不过,好像有点困难,所以请帮助他!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。

保证对于每个 $$$1 \le i \lt n$$$,$$$a_i \neq a_{i+1}$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,表示使数组严格递增的最小操作数。

示例

输入
复制

4
3
3 2 1
3
3 1 2
4
-2 -5 5 2
7
1 9 1 9 8 1 0

输出
复制

2
1
1
3

注意

在第一个测试用例中,获得最小操作数的可能方法:

  • 在第一个操作中,选择$$$l = 2,r = 2$$$和$$$a'_2 = 4$$$,则$$$a=[3, 4, 1]$$$;
  • 在第二个操作中,选择 $$$l = 1、r = 2$$$ 和 $$$a'_1 = -1、a'_2 = 0$$$,然后 $$$a=[-1, 0, 1]$$$。

在第二个测试用例中,获得最小操作数的可能方法:

  • 在第一个操作中,选择 $$$l = 2、r = 3$$$ 和 $$$a'_2 = 4、a'_3 = 5$$$,然后 $$$a = [3, 4, 5]$$$。

在第三个测试用例中,获得最小操作数的一种可能方法:

  • 在第一个操作中,选择 $$$l = 2、r = 3$$$ 和 $$$a'_2 = -1、a'_3 = 1$$$,然后 $$$a = [-2, -1, 1, 2]$$$。