{"problem":{"name":"K. The Dragon and the Kingdom of Trees","description":{"content":"Ayoub hates King Mahmoud, who is the king of a very large kingdom that is famous for planting very tall trees. King Mahmoud started a new plan to plant $n$ trees, so he planted $n$ seeds in $n$ conse","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10241K"},"statements":[{"statement_type":"Markdown","content":"Ayoub hates King Mahmoud, who is the king of a very large kingdom that is famous for planting very tall trees.\n\nKing Mahmoud started a new plan to plant $n$ trees, so he planted $n$ seeds in $n$ consecutive places. Initially, the height of every tree is $0$ units.\n\nEvery year the height of every tree increases by one unit, but in some years Ayoub comes and chooses exactly $k$ non-intersecting sub-arrays of trees and attack them with his dragon.\n\nWhen a tree is attacked the seed won't be affected, so it can grow again, but its height becomes \"0\".\n\nKing Mahmoud came after $m$ years and found that the height of the $i_{t h}$ tree is $h_i$ units.\n\nKing Mahmoud noticed that in some years Ayoub's dragon came and attacked the plants. King Mahmoud became very angry and decided to attack Ayoub with his army.\n\nAyoub is very powerful with his dragon but King Mahmoud has a strategy to take down Ayoub, but he needs to know the minimum possible $k$ so that the heights of the trees are correct.\n\nKing Mahmoud knows that Ayoub attacked at least once, it can also happen that Ayoub attacked immediately after they planted the seeds in the first year.\n\nIt can happen that there is no possible $k$, in that case, Ayoub has cheated and used a different way to attack King Mahmoud's plants, in this case, King's Mahmoud strategy will fail so he won't attack Ayoub.\n\nThe first line contains two integers $n$ and $m$ $(1 <= n <= 10^6)$ $(1 <= m <= 10^9)$.\n\nThe second line contains $n$ integers, the $i_{t h}$ one is $h_i$ which is the height of the $i_{t h}$ $(0 <= h_i <= m)$ plant after $m$ years.\n\nIf there is no possible $k$ print _-1_, otherwise print the minimum possible $k$ on a line.\n\n## Input\n\nThe first line contains two integers $n$ and $m$ $(1 <= n <= 10^6)$ $(1 <= m <= 10^9)$.The second line contains $n$ integers, the $i_{t h}$ one is $h_i$ which is the height of the $i_{t h}$ $(0 <= h_i <= m)$ plant after $m$ years.\n\n## Output\n\nIf there is no possible $k$ print _-1_, otherwise print the minimum possible $k$ on a line.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $, with $ 1 \\leq n \\leq 10^6 $, $ 1 \\leq m \\leq 10^9 $.  \nLet $ H = (h_1, h_2, \\dots, h_n) $ be a sequence of integers with $ 0 \\leq h_i \\leq m $ for all $ i \\in \\{1, \\dots, n\\} $.\n\n**Constraints**  \nEach $ h_i $ represents the final height of tree $ i $ after $ m $ years, where:  \n- Initially, all trees have height 0.  \n- Each year, all trees grow by 1 unit unless attacked.  \n- In some years, Ayoub selects exactly $ k $ non-intersecting contiguous subarrays and resets the height of all trees in those subarrays to 0.  \n- Ayoub attacks at least once.  \n\n**Objective**  \nFind the minimum integer $ k \\geq 1 $ such that $ H $ can be produced by exactly $ k $ attacks (each resetting a set of non-overlapping contiguous subarrays) over $ m $ years.  \nIf no such $ k $ exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10241K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}