535. K Empty Slots

There are n bulbs in a row, all off. The array bulbs is a permutation of 1..n: on day i (1-indexed) the bulb at position bulbs[i-1] turns on. Return the earliest day on which there exist two on-bulbs with exactly k bulbs between them that are all still off, or -1 if it never happens. The input is JSON {bulbs, k}.

Input: JSON {bulbs, k}.

Output: Integer — the earliest day, or -1.

Examples

Input: {"bulbs":[1,3,2],"k":1}
Output: 2
Explanation: On day 2, bulbs 1 and 3 are on with bulb 2 off between them.

Input: {"bulbs":[1,2,3],"k":1}
Output: -1
Explanation: Never two on-bulbs with one off between.

Input: {"bulbs":[1],"k":0}
Output: -1
Explanation: Only one bulb.

Constraints

• 1<=n<=2*10^4
• bulbs is a permutation of 1..n
• 0<=k<=n

Asked by