{"id":"519572f7-a367-4de0-b50a-822a29285cf0","name":"K Increasing Subsequence 2","description":"For the given sequence A with n elements find the number of strictly increasing subsequences with k elements.\r\n\r\nNote: This question is same as K Increasing Subsequence, but this time array can have numbers from 1 to 10^9 and can have duplicates.","inputFormat":"First line contains two integer n and k\r\nfollowing n lines contains elements of sequence\r\nA[1]\r\nA[2]\r\n....A[n]","outputFormat":"Print one number the andwer to question","constraints":"1. 1 &lt;= n &lt;= 10^5\r\n2. 1 &lt;= k &lt;= 11\r\n3. 1 &lt;= A[i] &lt;= 10^9\r\n5. A can contain duplicates\r\n6. Output may not fit in 32 bit signed integer","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n String inp[] = read.readLine().split(\" \");\r\n int n = Integer.parseInt(inp[0]);\r\n int k = Integer.parseInt(inp[1]);\r\n\r\n int ar[] = new int[n];\r\n\r\n for (int i = 0; i < n; i++) {\r\n ar[i] = Integer.parseInt(read.readLine());\r\n }\r\n // write your code here\r\n\r\n\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"5 2\r\n1\r\n1\r\n3\r\n8\r\n2\r\n","sampleOutput":"7\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9b3d7d76-b2ca-458f-80a8-4b37d548024a","name":"Segment Tree For Experts","slug":"segment-tree-for-experts-953","type":0},{"id":"4379e5e8-9f34-4397-9608-726fa2714fc1","name":"K Increasing Subsequence 2","slug":"k-increasing-subsequence-2","type":1}],"next":{"id":"c72de273-9722-456e-90e6-15f17dff887f","name":"Pillars","type":1,"slug":"pillars"},"prev":{"id":"9c7b50cd-8df3-4aff-b492-b2e6316f4682","name":"K Increasing Subsequence 1","type":1,"slug":"k-increasing-subsequence-1"}}}

K Increasing Subsequence 2

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.

{"id":"519572f7-a367-4de0-b50a-822a29285cf0","name":"K Increasing Subsequence 2","description":"For the given sequence A with n elements find the number of strictly increasing subsequences with k elements.\r\n\r\nNote: This question is same as K Increasing Subsequence, but this time array can have numbers from 1 to 10^9 and can have duplicates.","inputFormat":"First line contains two integer n and k\r\nfollowing n lines contains elements of sequence\r\nA[1]\r\nA[2]\r\n....A[n]","outputFormat":"Print one number the andwer to question","constraints":"1. 1 &lt;= n &lt;= 10^5\r\n2. 1 &lt;= k &lt;= 11\r\n3. 1 &lt;= A[i] &lt;= 10^9\r\n5. A can contain duplicates\r\n6. Output may not fit in 32 bit signed integer","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n BufferedReader read = new BufferedReader(new InputStreamReader(System.in));\r\n\r\n String inp[] = read.readLine().split(\" \");\r\n int n = Integer.parseInt(inp[0]);\r\n int k = Integer.parseInt(inp[1]);\r\n\r\n int ar[] = new int[n];\r\n\r\n for (int i = 0; i < n; i++) {\r\n ar[i] = Integer.parseInt(read.readLine());\r\n }\r\n // write your code here\r\n\r\n\r\n }\r\n}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"5 2\r\n1\r\n1\r\n3\r\n8\r\n2\r\n","sampleOutput":"7\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9b3d7d76-b2ca-458f-80a8-4b37d548024a","name":"Segment Tree For Experts","slug":"segment-tree-for-experts-953","type":0},{"id":"4379e5e8-9f34-4397-9608-726fa2714fc1","name":"K Increasing Subsequence 2","slug":"k-increasing-subsequence-2","type":1}],"next":{"id":"c72de273-9722-456e-90e6-15f17dff887f","name":"Pillars","type":1,"slug":"pillars"},"prev":{"id":"9c7b50cd-8df3-4aff-b492-b2e6316f4682","name":"K Increasing Subsequence 1","type":1,"slug":"k-increasing-subsequence-1"}}}
plane

Editor

Loading...

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

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode