Good Subarray
Contest: Kotlin Heroes: Episode 11
Tags: *special, data structures, greedy

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.

Input format:
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$$$.

Output format:
For each test case, print a single integer — the number of good contiguous subarrays of the array $$$a$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first example, the following four subarrays are good:

- from the $$$1$$$-st to the $$$1$$$-st element;
- from the $$$1$$$-st to the $$$2$$$-nd element;
- from the $$$2$$$-nd to the $$$2$$$-nd element;
- from the $$$3$$$-rd to the $$$3$$$-rd element.

In the second example, the only subarray which is not good is the subarray from the $$$3$$$-rd element to the $$$4$$$-th element.

Example input:
4
3
1 1 3
4
3 2 3 1
1
1
8
4 5 6 5 3 2 3 1

Example output:
4
9
1
23

Editorial:
Let's calculate the array $$$\mathit{prev}_i$$$ — the nearest element to the left of $$$i$$$ that can add the $$$i$$$-th element during the execution of the algorithm (i.e., the nearest value to the left among $$$(a_i-1)$$$, $$$a_i$$$, and $$$(a_i+1)$$$).
Note that a subarray $$$[l, r]$$$ is good if there is no index $$$j$$$ such that $$$l < j \le r$$$, and $$$\mathit{prev}_j < l$$$. It follows that for a fixed left boundary $$$l$$$, we need to find the minimum $$$j$$$ for which the above conditions hold, and then the answer can be increased by $$$(j - l)$$$, since $$$r \in [l, j)$$$ are good.
Using that fact, we can iterate over the left boundary of the segment $$$l$$$ from right to left. And maintain a stack of all indices $$$j$$$ such that $$$j > l$$$ and $$$\mathit{prev}_j < l$$$. If the value at the top of the stack no longer satisfies this condition when moving to the next value of $$$l$$$, it can be removed (since the condition doesn't hold for all next $$$l$$$ either). After that, the top of the stack contains the minimum $$$j$$$, that allows us to update the answer (if the stack is empty, any right boundary is good). After that, it is sufficient to push the index $$$l$$$ onto the stack and move to the next value.
Thus, we have obtained a solution that works in $$$O(n)$$$.