FastPrep

Description

Solutions

Sum of Compressed Number for All Subarrays

🔥 FULLTIME📚RELATED PROBLEMS

You are given an array a of size n. The compressed version of an array is defined as replacing the occurrence of consecutive equal integers with the single occurrence.

Example: For a = [1, 1, 2, 2, 1, 1], the compressed version will be [1, 2, 1].

The compressed number of an array is defined as the number of ways to remove some non-empty subsequence of indexes from the initial array to make it compressed. Two ways are considered different if the sequence of indexes deleted from the array was different, the order of removing does not matter.

Calculate the sum of compressed number for all subarrays of the array a. Since the sum may be large, print it modulo 10^9 + 7.

Function Description

Complete the function sumOfCompressedNumbers in the editor.

sumOfCompressedNumbers has the following parameter:

int a[n]: an array of integers

Returns

int: the sum of compressed number for all the subarrays of the array a modulo 10^9 + 7

Example 1:

Input:  a = [6, 7, 3, 6, 6]
Output: 8 
Explanation:

We have a = [6, 7, 3, 6, 6]. The subarrays of a with their respective compressed numbers are as follows:
   
      
        [6] has compressed number 0 as it is already compressed.
        Similarly, [6, 7], [6, 7, 3], [6, 7, 3, 6] have compressed number 0 as they are already compressed.
        [6, 7, 3, 6, 6] has compressed number 2 as we can delete either index 4 or index 5 to get compressed version [6, 7, 3, 6].
        [7], [7, 3], [7, 3, 6] have compressed number 0 as they are already compressed.
        [7, 3, 6, 6] has compressed number 2.
        [3], [3, 6] have compressed number 0 as they are already compressed.
        [3, 6, 6] has compressed number 2.
        [6] has compressed number 0 as it is already compressed.
        [6, 6] has compressed number 2.
        [6] has compressed number 0 as it is already compressed.
      
  
So, the total sum of all compressed numbers of all subarrays of a = 8.

Example 2:

Input:  a = [4, 4]
Output: 2 
Explanation:

We have a = [4, 4]. The subarrays of a with their respective compressed numbers are as follows:
  
      
        [4] has compressed number 0 as it is already compressed.
        [4, 4] has compressed number 2 as we can delete either index 1 or index 2 to get compressed version [4].
      
     
So, the sum of compressed number = 2.

Example 3:

Input:  a = [3, 3, 3, 3]
Output: 16 
Explanation:
There are 4 subarrays of type . The compressed number is 0 as it is already compressed.

There are 3 subarrays of type . The compressed number is 2 as either of the index can be deleted. So, the sum of compressed number would be 6.

There are 2 subarrays of type . the compressed number is 3 as either of the sequence of indices  or  can be deleted. So, the sum of compressed number would be 6.

There is 1 subarray  with the compressed number 4.

So, the sum of compressed number of all subarrays is 16.

Constraints:

1 ≤ t ≤ 10
1 ≤ n ≤ 10^5
1 ≤ a[i] ≤ 10^5