{"problem":{"name":"F. Row of Models","description":{"content":"During the final part of fashion show all models come to the stage and stay in one row and fashion designer stays to right to model on the right. During the rehearsal, Izabella noticed, that row isn't","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF887F"},"statements":[{"statement_type":"Markdown","content":"During the final part of fashion show all models come to the stage and stay in one row and fashion designer stays to right to model on the right. During the rehearsal, Izabella noticed, that row isn't nice, but she can't figure out how to fix it.\n\nLike many other creative people, Izabella has a specific sense of beauty. Evaluating beauty of row of models Izabella looks at heights of models. She thinks that row is nice if for each model distance to nearest model with less height (model or fashion designer) to the right of her doesn't exceed _k_ (distance between adjacent people equals 1, the distance between people with exactly one man between them equals 2, etc).\n\nShe wants to make row nice, but fashion designer has his own sense of beauty, so she can at most one time select two models from the row and swap their positions if the left model from this pair is higher than the right model from this pair.\n\nFashion designer (man to the right of rightmost model) has less height than all models and can't be selected for exchange.\n\nYou should tell if it's possible to make at most one exchange in such a way that row becomes nice for Izabella.\n\n## Input\n\nIn first line there are two integers _n_ and _k_ (1 ≤ _n_ ≤ 5·105, 1 ≤ _k_ ≤ _n_) — number of models and required distance.\n\nSecond line contains _n_ space-separated integers _a__i_ (1 ≤ _a__i_ ≤ 109) — height of each model. Pay attention that height of fashion designer is not given and can be less than 1.\n\n## Output\n\nPrint «_YES_» (without quotes) if it's possible to make row nice using at most one exchange, and «_NO_» (without quotes) otherwise.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在时装秀的最后阶段，所有模特走上舞台并排成一排，时尚设计师站在最右侧模特的右侧。在彩排时，伊扎贝拉注意到这一排不够美观，但她无法找出如何修复它。\n\n像许多其他有创造力的人一样，伊扎贝拉有着独特的审美观。在评估模特排的美观度时，她关注的是模特的身高。她认为，如果对于每个模特，其右侧最近的、身高比她更矮的模特（或时尚设计师）的距离不超过 $k$（相邻两人之间的距离为 1，中间恰好隔一个人的两人之间距离为 2，依此类推），那么这排就是美观的。\n\n她希望使这排变得美观，但时尚设计师也有自己的审美标准，因此她最多只能进行一次交换：从行中选出两个模特，交换它们的位置，且仅当左侧模特的身高高于右侧模特时才允许交换。\n\n时尚设计师（位于最右模特右侧的男性）的身高比所有模特都矮，且不能被选中参与交换。\n\n你需要判断是否可以通过至多一次交换，使这排变得对伊扎贝拉而言是美观的。\n\n第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 5·10^5$，$1 ≤ k ≤ n$）——模特的数量和要求的距离。\n\n第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1 ≤ a_i ≤ 10^9$）——每个模特的身高。请注意，时尚设计师的身高未给出，且可能小于 1。\n\n## Input\n\n在第一行包含两个整数 $n$ 和 $k$（$1 ≤ n ≤ 5·10^5$，$1 ≤ k ≤ n$）——模特的数量和要求的距离。第二行包含 $n$ 个用空格分隔的整数 $a_i$（$1 ≤ a_i ≤ 10^9$）——每个模特的身高。请注意，时尚设计师的身高未给出，且可能小于 1。\n\n## Output\n\n如果可以通过至多一次交换使这排变得对伊扎贝拉而言是美观的，请输出 «_YES_»（不含引号），否则输出 «_NO_»（不含引号）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ and $ k $ be positive integers with $ 1 \\leq n \\leq 5 \\cdot 10^5 $ and $ 1 \\leq k \\leq n $.  \nLet $ a = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers representing the heights of $ n $ models, ordered left to right in a row.  \nLet $ a_{n+1} = 0 $ represent the height of the fashion designer, positioned immediately to the right of the rightmost model, with $ a_{n+1} < \\min_{1 \\leq i \\leq n} a_i $.\n\nFor each model $ i \\in \\{1, 2, \\dots, n\\} $, define $ d_i $ as the distance to the nearest person to the right (including the fashion designer) with strictly smaller height:  \n$$\nd_i = \\min \\{ j - i \\mid j > i,\\ a_j < a_i \\}\n$$  \nIf no such $ j $ exists, then $ d_i = \\infty $ (but by assumption, $ a_{n+1} = 0 < a_i $, so $ d_i \\leq n+1-i $).\n\nThe row is *nice* if for all $ i \\in \\{1, \\dots, n\\} $, $ d_i \\leq k $.\n\nWe are allowed to perform **at most one swap**: choose indices $ i < j $ such that $ a_i > a_j $, and swap $ a_i $ and $ a_j $. The fashion designer cannot be involved.\n\n**Objective:** Determine whether there exists a pair $ (i, j) $ with $ 1 \\leq i < j \\leq n $ and $ a_i > a_j $, such that after swapping $ a_i $ and $ a_j $, the resulting sequence $ a' $ satisfies $ d'_\\ell \\leq k $ for all $ \\ell \\in \\{1, \\dots, n\\} $, where $ d'_\\ell $ is defined analogously for $ a' $.\n\n---\n\n**Formal Statement:**\n\nGiven:\n- $ n, k \\in \\mathbb{Z}^+ $, $ 1 \\leq n \\leq 5 \\cdot 10^5 $, $ 1 \\leq k \\leq n $\n- $ a \\in \\mathbb{Z}^n $, $ a_i \\geq 1 $\n\nDefine $ a_{n+1} = 0 $.  \nFor $ i \\in [1, n] $, define:\n$$\nd_i(a) = \\min \\{ j - i \\mid j \\in \\{i+1, \\dots, n+1\\},\\ a_j < a_i \\}\n$$\n\nDefine the set of *violations*:\n$$\nV(a) = \\{ i \\in [1, n] \\mid d_i(a) > k \\}\n$$\n\nWe are to determine:\n$$\n\\exists\\ (i, j) \\in [1, n]^2,\\ i < j,\\ a_i > a_j,\\ \\text{such that}\\ V(a') = \\emptyset\n$$\nwhere $ a' $ is the sequence obtained by swapping $ a_i $ and $ a_j $ in $ a $, and $ a'_\\ell = a_\\ell $ for $ \\ell \\notin \\{i, j\\} $, $ a'_i = a_j $, $ a'_j = a_i $.\n\nOutput \"YES\" if such a swap exists, \"NO\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF887F","tags":["greedy","sortings"],"sample_group":[["5 4\n2 3 5 2 5","NO"],["5 2\n3 6 2 2 1","YES"],["5 2\n5 3 6 5 2","YES"]],"created_at":"2026-03-03 11:00:39"}}