乘法排序

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的正整数数组 $a$。一次操作可以选择 $1\le l\le r\le n$ 和任意整数 $x$，把区间 $[l,r]$ 中的每个元素都乘以 $x$。整数 $x$ 可以为负数。

求至少需要多少次操作，才能使数组严格递增。

输入格式

第一行包含测试组数 $t$（$1\le t\le 10^4$）。

每组数据第一行包含一个整数 $n$（$1\le n\le 2\times10^5$），第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le10^9$）。

所有测试组的 $n$ 之和不超过 $2\times10^5$。

输出格式

对每组数据输出一个整数，表示所需的最少操作次数。

样例输入 1

3
5
1 1 2 2 2
6
5 4 3 2 5 1
3
1 2 3

样例输出 1

3
2
0

数据范围

对于所有数据，$1\le t\le10^4$，$1\le n\le2\times10^5$，$1\le a_i\le10^9$，且所有测试组的 $n$ 之和不超过 $2\times10^5$。