heights of length n. You are given an integer stride. The row is ordered at stride stride if heights[i - stride] ≤ heights[i] holds for every i from stride to n - 1.
For example, the row [5, 2, 6, 2, 7] is ordered at stride 2 (5 ≤ 6 ≤ 7 and 2 ≤ 2) but not at stride 1.
In one operation you may replace the height of any post with any positive integer. Return the smallest number of operations that makes the row ordered at stride stride.heights=[3, 8, 1, 9, 2, 10], stride=2 → 1
The chain at positions 0, 2, 4 is [3, 1, 2]: replacing 3 with, say, 1 is enough. The chain 1, 3, 5 is [8, 9, 10], already non-decreasing. One change in total.
heights=[4, 3, 2, 1], stride=1 → 3
With stride 1 the whole row must be non-decreasing. Only one post can stay, so the other three must be replaced.
heights=[2, 1, 2], stride=3 → 0
The stride exceeds every gap between positions, so there is nothing to compare and nothing to change.
n ≤ 10⁵heights[i] ≤ 10⁹stride ≤ nheights=[3, 8, 1, 9, 2, 10], stride=2
1
Run checks the first 3 tests in your browser. Submit checks all 129 tests on the server, hidden ones included.