A sequence of numbers is said to be good if it satisfies the following two conditions:
- All elements in the sequence are unique.
- If the minimum element in the sequence is
a, and the maximum element in the sequence isb, then all numbers in the range [a,b] are present in the sequence.
For example, (4, 2, 5, 1, 3) is a good sequence, while (2, 2, 1) or (3, 7) are not.
A subsequence of an array arr is a sequence that can be derived from the array arr by deleting some or no elements without changing the order of the remaining elements. Given an array of n integers, find the number of different good subsequences. Two subsequences are considered different if they include at least one different index. For example, for the sequence (2, 2, 1), both (2, 1) formed by indices 1 and 2 and (2, 1) formed by indices 0 and 2 are considered different subsequences.
Function Description
Complete the function countGoodSubsequences in the editor.
countGoodSubsequences has the following parameter:
int arr[n]: the given array of integersReturns
long integer: the number of good subsequences which can be derived from the array.
Example 1:
Input: arr = [13, 11, 4, 12, 5, 4]
Output: 11
Explanation:We can form the following good subsequences:Subsequences of length 1: [13], [11], [4], [12], [5], [4] Subsequences of length 2: [13, 12], [11, 1], [12, 4], [5, 4] Subsequences of length 3: [13, 11, 12] Thus, the answer is 6 + 4 + 1 = 11.
1 ≤ n ≤ 10^51 ≤ arr[i] ≤ 10^5, for alli
input:
output: