CF1661D Progressions Covering

You are given two arrays: an array $ a $ consisting of $ n $ zeros and an array $ b $ consisting of $ n $ integers. You can apply the following operation to the array $ a $ an arbitrary number of times: choose some subsegment of $ a $ of length $ k $ and add the arithmetic progression $ 1, 2, \ldots, k $ to this subsegment — i. e. add $ 1 $ to the first element of the subsegment, $ 2 $ to the second element, and so on. The chosen subsegment should be inside the borders of the array $ a $ (i.e., if the left border of the chosen subsegment is $ l $ , then the condition $ 1 \le l \le l + k - 1 \le n $ should be satisfied). Note that the progression added is always $ 1, 2, \ldots, k $ but not the $ k, k - 1, \ldots, 1 $ or anything else (i.e., the leftmost element of the subsegment always increases by $ 1 $ , the second element always increases by $ 2 $ and so on). Your task is to find the minimum possible number of operations required to satisfy the condition $ a_i \ge b_i $ for each $ i $ from $ 1 $ to $ n $ . Note that the condition $ a_i \ge b_i $ should be satisfied for all elements at once.

The first line of the input contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 3 \cdot 10^5 $ ) — the number of elements in both arrays and the length of the subsegment, respectively. The second line of the input contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le 10^{12} $ ), where $ b_i $ is the $ i $ -th element of the array $ b $ .

Print one integer — the minimum possible number of operations required to satisfy the condition $ a_i \ge b_i $ for each $ i $ from $ 1 $ to $ n $ .

Consider the first example. In this test, we don't really have any choice, so we need to add at least five progressions to make the first element equals $ 5 $ . The array $ a $ becomes $ [5, 10, 15] $ . Consider the second example. In this test, let's add one progression on the segment $ [1; 3] $ and two progressions on the segment $ [4; 6] $ . Then, the array $ a $ becomes $ [1, 2, 3, 2, 4, 6] $ .