{"problem":{"name":"H. Count Subarrays","description":{"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. Inversions in a subarray Ai, Ai + 1,..., A","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10058H"},"statements":[{"statement_type":"Markdown","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## Input\n\nFirst line consists of N and K in single line. Next line contains N space separated integers denoting array A.\n\n## Output\n\nPrint the required answer in one line.*Constraints*   1 ≤ N ≤ 105  0 ≤ Ai ≤ 109  0 ≤ K ≤ N * (N - 1) / 2 \n\n[samples]\n\n## Note\n\nLet’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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10058H","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}