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.
Constraints
1. 1 <= n <= 10^5 2. 1 <= k <= 11 3. 1 <= A[i] <= 10^9 5. A can contain duplicates 6. Output may not fit in 32 bit signed integer
Format
Input
First line contains two integer n and k following n lines contains elements of sequence A[1] A[2] ....A[n]
Output
Print one number the andwer to question
Example
Sample Input
5 2
1
1
3
8
2
Sample Output
7