Codeforces Round 969 (Div. 1) |
---|
Finished |
Let there be a set that contains distinct positive integers. To expand the set to contain as many integers as possible, Eri can choose two integers x≠y from the set such that their average x+y2 is still a positive integer and isn't contained in the set, and add it to the set. The integers x and y remain in the set.
Let's call the set of integers consecutive if, after the elements are sorted, the difference between any pair of adjacent elements is 1. For example, sets {2}, {2,5,4,3}, {5,6,8,7} are consecutive, while {2,4,5,6}, {9,7} are not.
Eri likes consecutive sets. Suppose there is an array b, then Eri puts all elements in b into the set. If after a finite number of operations described above, the set can become consecutive, the array b will be called brilliant.
Note that if the same integer appears in the array multiple times, we only put it into the set once, as a set always contains distinct positive integers.
Eri has an array a of n positive integers. Please help him to count the number of pairs of integers (l,r) such that 1≤l≤r≤n and the subarray al,al+1,…,ar is brilliant.
Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer n (1≤n≤4⋅105) — length of the array a.
The second line of each test case contains n integers a1,a2,…an (1≤ai≤109) — the elements of the array a.
It is guaranteed that the sum of n over all test cases doesn't exceed 4⋅105.
For each test case, output a single integer — the number of brilliant subarrays.
622 261 3 6 10 15 2156 30 18 36 91100000000061 1 4 5 1 41270 130 90 90 90 108 612 500 451 171 193 193
3 18 5 1 18 53
In the first test case, the array a=[2,2] has 3 subarrays: [2], [2], and [2,2]. For all of them, the set only contains a single integer 2, therefore it's always consecutive. All these subarrays are brilliant, so the answer is 3.
In the second test case, let's consider the subarray [3,6,10]. We can do operations as follows:
{3,4,5,6,7,8,9,10} is a consecutive set, so the subarray [3,6,10] is brilliant.
Name |
---|