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
2 3 1 1 2 5 2 2 3 2 1
4 12
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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor