{"problem":{"name":"G. Underpalindromity","description":{"content":"Let us call _underpalindromity_ of array b of length k the minimal number of times one need to increment some elements bj by 1 so that the array b would become a palindrome, that is, b1 = bk, b2 = bk ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10175G"},"statements":[{"statement_type":"Markdown","content":"Let us call _underpalindromity_ of array b of length k the minimal number of times one need to increment some elements bj by 1 so that the array b would become a palindrome, that is, b1 = bk, b2 = bk - 1, and so on.\n\nThe array of length n, consisting of integers, is given. Consider all its subarrays of length k, and for each of these subarrays its _underpalindromity_ pi. It's needed to calculate sum of all pi (1 ≤ i ≤ n - k + 1).\n\nThe first line contains two integers n and k (1 ≤ k ≤ n ≤ 200000) — the length of the array and the length of subarrays.\n\nThe second line contains n integers ai ( - 108 ≤ ai ≤ 108) — the elements of the array.\n\nOutput a single integer — sum of _underpalindromities_ of all subarrays of length k.\n\n## Input\n\nThe first line contains two integers n and k (1 ≤ k ≤ n ≤ 200000) — the length of the array and the length of subarrays.The second line contains n integers ai ( - 108 ≤ ai ≤ 108) — the elements of the array.\n\n## Output\n\nOutput a single integer — sum of _underpalindromities_ of all subarrays of length k.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k \\leq n \\leq 200000 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in [-10^8, 10^8] $.  \n\nFor a subarray $ B_i = (a_i, a_{i+1}, \\dots, a_{i+k-1}) $ of length $ k $, define its **underpalindromity** $ p_i $ as:  \n$$\np_i = \\sum_{j=1}^{\\lfloor k/2 \\rfloor} \\left| a_{i+j-1} - a_{i+k-j} \\right|\n$$\n\n**Constraints**  \n1. $ 1 \\leq k \\leq n \\leq 200000 $  \n2. $ -10^8 \\leq a_i \\leq 10^8 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCompute:  \n$$\n\\sum_{i=1}^{n - k + 1} p_i = \\sum_{i=1}^{n - k + 1} \\sum_{j=1}^{\\lfloor k/2 \\rfloor} \\left| a_{i+j-1} - a_{i+k-j} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10175G","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}