Distinct Values solution codechef

Distinct Values solution codechef – The beauty value of an array is defined as the difference between the largest and second largest elements of the array. Note that the largest and second largest elements can have the same value in case of duplicates.

Distinct Values solution codechef

For example, beauty value of [2,5,3,1]=5−3=2 and beauty value of [7,6,7]=7−7=0

You are given an array  of length . Your task is to find the total number of distinct beauty values among all subarrays of  having length greater than 1.

Note that, a subarray is obtained by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the array.

Input Format

  • The first line of input will contain a single integer , denoting the number of test cases.
  • Each test case consists of two lines of input.
    • The first line of each test case contains a single integer  — the size of the array.
    • The second line contains  space-separated numbers – �1,�2,…,��, the elements of the array.

Output Format

For each test case, output a single line, the total number of distinct beauty among all subarrays of  having length greater than 1.

Distinct Values solution codechef

  • 1≤�≤104
  • 2≤�≤2⋅105
  • 1≤��≤109
  • Sum of  over all test cases does not exceed 2⋅105.

Sample 1:

Input

Output

4
2
1 1
3
4 2 1
4
8 1 7 2
5
6 9 4 2 1
1
2
4
4

 

 

Distinct Values solution codechef

Test case 1: The only subarray is [1,1] whose beauty is 0. Thus, there is only 1 distinct value of beauty.

Test case 2: The subarrays are [4,2],[2,1], and [4,2,1] having beauty 2,1, and 2 respectively. There are 2 distinct values of beauty.

Test case 3: The unique values of beauty are 7,1,6, and 5.

Test case 4: The unique values of beauty are 3,5,2, and 1.

Leave a Reply

Your email address will not be published. Required fields are marked *