P17717 [LAOI Round 21] 拼积木 / block

题目来源：【HT-130-Div.3】核桃 CSP-J 组模拟赛 [LAOI](https://www.luogu.com.cn/team/48237) 欢迎您。

在变完魔术以后，小 Hex 和小 Toast 又开始玩起了他的积木。 小 Hex 把他的所有积木整理起来，按美丽度**从大到小**的顺序把他的所有积木排成一行。此时排序后第 $i$ 块积木的美丽度为 $b_i$。现在小 Hex 想把他的一段连续区间的所有积木拼成一座积木塔，并邀请小 Toast 观赏。 然而小 Toast 对积木塔有着独特的审美。小 Toast 计算一段区间 $[l,r]$ 的积木的「奇异值（$t$）」的方法如下： - 首先，小 Hex 拿出了第 $l$ 块积木 - 此时令 $t=a_l$。 - 接下来，小 Hex 会依次将第 $l+1$，第 $l+2$，$\cdots$，第 $r$ 块积木拼在现有的积木塔上。假设小 Hex 目前在拼接第 $i$ 块积木。 - 此时令 $t\gets \lfloor\frac{\max(t,a_i)}{\min(t,a_i)}\rfloor$。 最终，如果奇异值 $t$ 为 $1$，那么小 Toast 则称这段区间是好的。现在小 Toast 想要知道，对于所有的 $1\leq l \leq r \leq n$，有多少段区间是好的？ #### 简要题意 多次询问，每次给定一个**单调不增**的序列 $b$，对于 $b$ 的一个非空区间 $[l,r]$，初始时令变量 $t=b_l$。从 $l+1$ 到 $r$ 枚举下标 $i$，依次执行操作 $t:=\lfloor\frac{\max(t,b_i)}{\min(t,b_i)}\rfloor$，所有操作完成后最终 $t=1$，则称这个区间是好的。 现询问 $A$ 有多少个非空区间是好的。

**本题有多组测试数据。** 第一行给定一个正整数 $T$，表示数据组数。 对于每组数据： - 第一行输入一个正整数 $n$，表示序列长度； - 第二行输入 $n$ 个正整数，表示序列 $b$。

共 $T$ 行，对于每组测试数据，输出一个整数表示答案。

#### 【样例 1 解释】 - 对于第一组测试数据，好的区间有 $[1,2]$、$[2,3]$； - 如果区间为 $[1,2]$，那么初始时 $t=3$，拼接第 $2$ 块积木时，$t\gets \lfloor\frac{\max(3,2)}{\min(3,2)}\rfloor=\lfloor\frac{3}{2}\rfloor=1$。因此这个区间是好的。 - 如果区间为 $[2,3]$，那么初始时 $t=2$，拼接第 $3$ 块积木时，$t\gets \lfloor\frac{\max(2,2)}{\min(2,2)}\rfloor=\lfloor\frac{2}{2}\rfloor=1$。因此这个区间是好的。 - 对于第二组测试数据，可以证明不存在好的区间。 - 对于第三组测试数据，好的区间有 $[1,2]$、$[1,4]$、$[2,3]$、$[1,5]$、$[3,4]$、$[3,5]$、$[5,5]$。 #### 【样例 3】 见选手目录下的 block/block3.in 与 block/block3.ans。 该样例满足测试点 $1$ 的约束条件。 #### 【样例 4】 见选手目录下的 block/block4.in 与 block/block4.ans。 该样例满足测试点 $2,3$ 的约束条件。 #### 【样例 5】 见选手目录下的 block/block5.in 与 block/block5.ans。 该样例满足测试点 $4\sim 6$ 的约束条件。 #### 【样例 6】 见选手目录下的 block/block6.in 与 block/block6.ans。 该样例满足测试点 $7,8$ 的约束条件。 #### 【样例 7】 见选手目录下的 block/block7.in 与 block/block7.ans。 该样例满足测试点 $9\sim 11$ 的约束条件。 #### 【样例 8】 见选手目录下的 block/block8.in 与 block/block8.ans。 该样例满足测试点 $12\sim 20$ 的约束条件。 #### 【数据范围】 对于所有测试数据，保证 $1\le T\le 10^6$，$1\le n,\sum n \le 10^6$，$1\le b_i\le 10^9$。 为表述方便，下面记 $\sum n$ 为测试点内所有 $n$ 之和。 ::cute-table{tuack} |测试点编号|$n,\sum n$|特殊性质| |:-:|:-:|:-:| |$1$|$\le 5\times 10^2$|无| |$2,3$|$\le 5\times 10^3$|无| |$4\sim 6$|$\le 10^6$| A | |$7,8$|^| B | |$9\sim 11$|^| C | |$12\sim 20$|^|无| 特殊性质 A：对于所有的 $i(1\leq i\leq n)$，保证 $b_i=n-i+1$。 特殊性质 B：保证所有的 $b_i$ 相同。 特殊性质 C：对于所有的 $i(1\leq i\leq n)$，保证 $1\leq b_i\leq 20$。