DSA Level 3 Competitive Segment Tree K Increasing Subsequence 2

K Increasing Subsequence 2

hard

For the given sequence A with n elements find the number of strictly increasing subsequences with k elements.

Note: This question is same as K Increasing Subsequence, but this time array can have numbers from 1 to 10^9 and can have duplicates.

Input Format

First line contains two integer n and k following n lines contains elements of sequence A[1] A[2] ....A[n]

Output Format

Print one number the andwer to question

Constraints

1. 1 &lt;= n &lt;= 10^5
2. 1 &lt;= k &lt;= 11
3. 1 &lt;= A[i] &lt;= 10^9
5. A can contain duplicates
6. Output may not fit in 32 bit signed integer

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

K Increasing Subsequence 1

Domino Principle