Make Permutation

★★★★★

4.9

7 votes

Advanced Data Structures, Segment tree, Data Structures, Segment Trees

Details

Submissions

Discussion

Editorial

Problem

A permutation is a sequence of integers from $1$ to $N$ of length $N$ containing each number exactly once. For example $(1), (4, 3, 5, 1, 2), (3, 2, 1)$ are permutations, and $(1, 1), (4, 3, 1), (2, 3, 4)$ are not.

An array $B$ is called good if it can be converted to a permutation by applying the following operation any number of times (possibly zero):

Choose an index $i$ of $B$ and a positive integer $x$ , then set $B_i = B_i - x.$

For example, the arrays $[1, 3, 5], [1, 3, 3], [2, 2]$ are good arrays while the arrays $[1, 2, 2], [2, 4, 1, 1]$ are not good.

You are given an array $A$ containing $N$ integers. Find the number of good subarrays of $A$ .

Input format

The first line contains $T$ denoting the number of test cases. The description of $T$ test cases is as follows:
For each test case:
- The first line contains a single integer $N$ denoting the size of array $A$ .
- The second line contains $N$ integers $A_1, A_2, \dots, A_N$ - denoting the elements of $A$ .

Output format

For each test case, print the answer in a separate line.

Constraints

$1 \le T \le 10^4 \\ 1 \leq N \leq 3\cdot 10^5\\ \\1\leq A_i \le N \\ \text {Sum of $N$ over all test cases does not exceed to }3\cdot 10^5$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In the first test case, the good subarrays are : $A[1\dots 1] = [1], A[2\dots 2] = [1], A[2\dots 3] = [1, 2], A[3\dots 3] = [2].$

In the second test case, there are $15$ subarrays of $A = [2, 2, 3, 2, 1]$ . All subarrays except $A[1\dots 4] = [2, 2, 3 ,2], A[1\dots 5] = [2, 2, 3, 2, 1], A[2\dots 5] = [2, 3, 2, 1]$ are good.