CF2226B Everything Everywhere

An array is called good if the difference between the maximum value and the minimum value in the array is equal to the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of all the elements in the array. Note that an empty array is considered to be not good. More formally, an array $ [a_1, a_2, \ldots, a_m] $ is good if and only if $$$ \max(a_1, a_2, \ldots, a_m) - \min(a_1, a_2, \ldots, a_m) = \gcd(a_1, a_2, \ldots, a_m).$$$ You are given a permutation $ ^{\text{∗}} $ $ p $ of length $ n $ . Determine the number of good subarrays $ ^{\text{†}} $ in the given permutation. $ ^{\text{∗}} $ A permutation of length $ m $ is an array consisting of $ m $ distinct integers from $ 1 $ to $ m $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ m=3 $ but there is $ 4 $ in the array). $ ^{\text{†}} $ An array $ b $ is a subarray of an array $ a $ if $ b $ can be obtained from $ a $ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each testcase contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the length of the permutation $ p $ . The second line of each testcase contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ) — the permutation $ p $ . It is guaranteed that $ p $ is a permutation. It is guaranteed that the sum of $ n $ over all the test cases does not exceed $ 2 \cdot 10^5 $ .

For each testcase, print a single integer — the number of good subarrays in the given permutation.

For the first testcase, only one subarray is good, which is $ [1, 2] $ . For the second testcase, it can be proven that no good subarrays exist in the given permutation.