**Problem Link**: ALORA6

**Author**: Rishup_nitdgp

**Tester**: Shivansh7

**Editorialist**: Aman0312

**Pre-Requisite**:Segment Trees or BIT.

**Problem**:Find the number of possible strictly increasing subsequences in the given sequence

such that the maximum element of this subsequence is at max k.

**Explanation**:

We will use the following notation:

S[i]:Number of strictly increasing subsequences in which maximum element is i.

Query_Operation(l,r): Sum of values from l to r in S array.

Update_operation(pos,val): Add val to S[pos].

n:Size of array.

When array size is x-1,S[i] denotes Number of strictly increasing subsequences in array of size

x-1 in which maximum element is i.

So when we add an element(array size becomes x) no. of strictly increasing subsequences in

which maximum element is a[x] is equal to (1+sum of all strictly increasing subsequences in

which maximum element is less than a[x]) which is nothing but Query_ Operation(1,a[x]-1);

Now we will update the values of S[a[x]] by Update_ Operation.

Initially all S[i] were zeroes.

After adding all elements S[i] denotes Number of strictly increasing subsequences in array of size

n in which maximum element is i.

We can perform update and query operations efficiently in O(log N) by segment trees

or BIT(Fenwick Tree) easily.

Queries:

Answer will be Query_operation(1,k) because we have to find the no. of

strictly increasing subsequences in which max element is ATMOST k.

But there is a problem,if array elements are equal to 1e9 we cannot make S array of size

1e9.We can use coordinate compression and make sure that array size will not

be greater than 1e5.

**Time Complexity**:T*(N logN +Q logN).

**Solution**: Link

**Setters Solution**:Link