Kotlin Heroes: Episode 11 |
---|
Finished |
You are given an integer array $$$a$$$ of size $$$n$$$.
Let's call an array good if it can be obtained using the following algorithm: create an array consisting of any single integer; and then perform the following operation an arbitrary number of times: choose an element from the already existing array (let's call it $$$x$$$) and add $$$x$$$, $$$(x-1)$$$, or $$$(x+1)$$$ to the end of the array.
For example, the arrays $$$[1, 2, 1]$$$, $$$[5]$$$ and $$$[3, 2, 1, 4]$$$ are good, while $$$[2, 4]$$$ and $$$[3, 1, 2]$$$ are not.
Your task is to count the number of good contiguous subarrays of the array $$$a$$$. Two subarrays that have the same elements but are in different positions of the array $$$a$$$ are considered different.
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$ 1 \le a_i \le n)$$$.
Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, print a single integer — the number of good contiguous subarrays of the array $$$a$$$.
431 1 343 2 3 11184 5 6 5 3 2 3 1
4 9 1 23
In the first example, the following four subarrays are good:
In the second example, the only subarray which is not good is the subarray from the $$$3$$$-rd element to the $$$4$$$-th element.
Name |
---|