A vineyard is laid out across n numbered terraces, each currently carved to a certain elevation measured in meters. The maintenance crew wants every terrace to end up at exactly the target elevation k, and terraces can only ever be cut down -- never built back up.
In one flattening round, the crew looks at the tallest elevation still present among any terrace, and lowers every terrace currently sitting at that exact elevation down to any elevation of the crew's choosing, as long as the new elevation is strictly less than the one being cut. Terraces that are not at the current tallest elevation are left untouched during that round.
Determine the minimum number of flattening rounds needed so that every terrace ends at elevation exactly k. If any terrace already sits below k, the goal can never be reached (since elevation can never be raised) -- report that case as -1.
Line 1: two integers n and k. Line 2: n integers elevation_1, elevation_2, ..., elevation_n -- the current elevation of each terrace.
Print a single integer: the minimum number of flattening rounds required, or -1 if the target is unreachable.
Example 1
Input
5 2 5 2 5 4 5
Expected
2
Explanation
The minimum elevation (2) is not below k=2, so the goal is reachable. The elevations strictly above k are {5, 4} -- two distinct tiers. Round 1 cuts every terrace at the tallest tier (5) down to 4, giving [4, 2, 4, 4, 4]; round 2 cuts the new tallest tier (4) down to 2, giving [2, 2, 2, 2, 2]. Two rounds are required and sufficient, so the answer is 2.
Example 2
Input
3 5 3 6 7
Expected
-1
Explanation
The minimum elevation in the array is 3, which is below the target k=5. Since terraces can only be cut lower, never raised, that terrace can never reach elevation 5, so the target is unreachable and the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →