Given a sequence of integers, find the number of ways to delete a non-empty subsequence such that the resulting sequence is non-empty and strictly increasing.
The subarray can be removed in 3 ways to form a strictly increasing sequence:
The subarray to be removed starts from first element
The subarray to be removed ends at last element
The subarray to be removed exist in between first and last element
The first and second subtask can be easily solved using prefix and suffix array.
The challenging part is to solve the 3rd subtask
To solve this part, for each valid index i which forms a strictly increasing sequcence starting from index i to last element, we need to compute the number of subarrays(to the left of index i) which starts from first element and forms a strictly increasing sequence ending with number less than number at index i (make sure this subarray doesn’t covers the whole left subarray).
This can be efficiently calculated using Fenwick Tree.
The sum of 1st, 2nd and 3rd subtask gives us the answer
Taking a example : 1 2 1 3 4
The subarrays possible for 1st subtask are :
- 1 3 4
- 3 4
For 2nd subtask :
- 1 2
Now for 3rd subtask :
- No need to check for 0 and 1 index(as we need to remove subarray that exist in between 1st and last element)
- for index 2 there doesn’t exist any strictly increasing subarray to the left, that ends at a element less than 1
- for index 3, there are two subarrays to the left of index 3 which are strictly increasing and ends at element less than 3, subarrays  and [1 2] -> adds 2 to the answer, resulting sequence can be [1 3 4] and [1 2 3 4]
- similarly for index 4, there exists two strictly increasing subarrays to the left,  and [1 2] - > again adds 2 to the answer, resulting sequence can be [1 4] and [1 2 4].
Hence the answer for this case is 3+2+2+2 = 9
As there can be at most 100000 distinct elements, so the elements can be easily mapped to fit onto Fenwick tree