CF1730E Maximums and Minimums

给定一个由正整数组成的数组 $a_1, a_2, \ldots, a_n$。 请你计算有多少对下标 $(l, r)$，其中 $1 \le l \le r \le n$，满足如下条件： 1. 在 $a_l, a_{l+1}, \ldots, a_r$ 中找到最小值和最大值。 2. 如果最大值能够被最小值整除，则该区间通过检查。

第一行包含一个整数 $t$（$1 \le t \le 10$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例包含两行。 第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^6$）。 保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示通过检查的下标对的数量。

下面 $x \mid y$ 表示 $y$ 能被 $x$ 整除。 在第一个测试用例中，只有一对 $(1, 1)$，最大值为 $1$，最小值也为 $1$，$1 \mid 1$，所以通过检查，答案为 $1$。 在第二个测试用例中，有 $3$ 个区间： - $(1, 1)$：最大值为 $2$，最小值为 $2$，$2 \mid 2$，通过检查。 - $(1, 2)$：最大值为 $4$，最小值为 $2$，$2 \mid 4$，通过检查。 - $(2, 2)$：最大值为 $4$，最小值为 $4$，$4 \mid 4$，通过检查。 在第三个测试用例中，有 $3$ 个区间： - $(1, 1)$：最大值为 $2$，最小值为 $2$，$2 \mid 2$，通过检查。 - $(1, 2)$：最大值为 $3$，最小值为 $2$，$3$ 不能被 $2$ 整除，未通过检查。 - $(2, 2)$：最大值为 $3$，最小值为 $3$，$3 \mid 3$，通过检查。 由 ChatGPT 4.1 翻译