{"id":"f4d1eed6-3e77-492f-a112-c468d8fea4e9","name":"K Increasing Subsequence 1","description":"For the given sequence A with n different elements find the number of increasing subsequences with k elements.","inputFormat":"First line contains one integer n\r\nSecond line contains one integer 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;= n\r\n4. 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 int n = Integer.parseInt(read.readLine());\r\n int k = Integer.parseInt(read.readLine());\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}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n3\r\n1\r\n2\r\n3\r\n5\r\n4\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":"9c7b50cd-8df3-4aff-b492-b2e6316f4682","name":"K Increasing Subsequence 1","slug":"k-increasing-subsequence-1","type":1}],"next":{"id":"4379e5e8-9f34-4397-9608-726fa2714fc1","name":"K Increasing Subsequence 2","type":1,"slug":"k-increasing-subsequence-2"},"prev":{"id":"d9f9a7f2-4b92-434b-8a57-8746d6170251","name":"Multiples Of 3","type":1,"slug":"multiples-of-3"}}}

K Increasing Subsequence 1

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

{"id":"f4d1eed6-3e77-492f-a112-c468d8fea4e9","name":"K Increasing Subsequence 1","description":"For the given sequence A with n different elements find the number of increasing subsequences with k elements.","inputFormat":"First line contains one integer n\r\nSecond line contains one integer 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;= n\r\n4. 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 int n = Integer.parseInt(read.readLine());\r\n int k = Integer.parseInt(read.readLine());\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}\r\n"},"ruby":{"code":""},"python":{"code":""},"javascript":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n3\r\n1\r\n2\r\n3\r\n5\r\n4\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":"9c7b50cd-8df3-4aff-b492-b2e6316f4682","name":"K Increasing Subsequence 1","slug":"k-increasing-subsequence-1","type":1}],"next":{"id":"4379e5e8-9f34-4397-9608-726fa2714fc1","name":"K Increasing Subsequence 2","type":1,"slug":"k-increasing-subsequence-2"},"prev":{"id":"d9f9a7f2-4b92-434b-8a57-8746d6170251","name":"Multiples Of 3","type":1,"slug":"multiples-of-3"}}}
plane

Editor

Loading...

K Increasing Subsequence 1

medium

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

Constraints

1. 1 <= n <= 10^5 2. 1 <= k <= 11 3. 1 <= A[i] <= n 4. Output may not fit in 32 bit signed integer

Format

Input

First line contains one integer n Second line contains one integer 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 3 1 2 3 5 4

Sample Output

7

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode