{"raw_statement":[{"iden":"statement","content":"Given an array of N integers A1, A2 ... AN and an integer K, count number of subarrays of A such that number of inversions in those subarrays is at least K.\n\nInversions in a subarray Ai, Ai + 1,..., Aj is defined as number of pairs (a, b) such that i ≤ a < b ≤ j and Aa > Ab.\n\nFirst line consists of N and K in single line. Next line contains N space separated integers denoting array A.\n\nPrint the required answer in one line.\n\n*Constraints* \n\nLet’s denote by A[i, j] the subarray Ai, Ai + 1 ... Aj.\n\nExample 1. A[1, 4, A[2, 4], A[3, 4]] have at least 1 inversion.\n\nExample 2. All subarrays are valid.\n\n"},{"iden":"input","content":"First line consists of N and K in single line. Next line contains N space separated integers denoting array A."},{"iden":"output","content":"Print the required answer in one line.*Constraints*   1 ≤ N ≤ 105  0 ≤ Ai ≤ 109  0 ≤ K ≤ N * (N - 1) / 2 "},{"iden":"examples","content":"Input4 11 2 4 0Output3Input2 01 2Output3"},{"iden":"note","content":"Let’s denote by A[i, j] the subarray Ai, Ai + 1 ... Aj.Example 1. A[1, 4, A[2, 4], A[3, 4]] have at least 1 inversion.Example 2. All subarrays are valid."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, K \\in \\mathbb{Z}^+ $.  \nLet $ A = (A_1, A_2, \\dots, A_N) $ be a sequence of integers.  \nFor a subarray $ A[i,j] = (A_i, A_{i+1}, \\dots, A_j) $ with $ 1 \\leq i \\leq j \\leq N $, define the number of inversions as:  \n$$\n\\text{inv}(i,j) = \\left| \\left\\{ (a,b) \\mid i \\leq a < b \\leq j \\text{ and } A_a > A_b \\right\\} \\right|\n$$\n\n**Constraints**  \n1. $ 1 \\leq N \\leq \\text{some upper bound (not specified)} $  \n2. $ 1 \\leq K \\leq \\binom{N}{2} $  \n3. $ A_i \\in \\mathbb{Z} $ for all $ i \\in \\{1, \\dots, N\\} $\n\n**Objective**  \nCount the number of subarrays $ A[i,j] $ such that:  \n$$\n\\text{inv}(i,j) \\geq K\n$$","simple_statement":"Given an array of N integers and an integer K, count how many subarrays have at least K inversions.  \nAn inversion is a pair (i, j) where i < j and A[i] > A[j].","has_page_source":false}