You are given a sequence of piano notes and a maximum hand span k. Each note is represented by its integer position on the keyboard.

During one hand placement, the difference between the leftmost and rightmost playable keys cannot exceed k. If the next note cannot be reached from the current placement, the hand must be lifted and positioned again.

Find the minimum number of hand placements required to play every note in the given order. The initial placement before playing the first note is counted.

Class

PianoHandPlanner

Method

minimumHandLifts

int minimumHandLifts(List<Integer> notes, int k)

Parameters

• notes: The keyboard positions of the notes in the order they must be played.
• k: The maximum allowed difference between the leftmost and rightmost keys covered by one hand placement.

Returns

Return the minimum number of hand placements required to play all the notes in sequence.

Rules

• The initial hand placement counts as one placement.
• The hand remains at the same placement until it is lifted.
• A consecutive group of notes can be played in one placement if the difference between its maximum and minimum positions is at most k.
• Notes must be played in their given order.
• Repeated notes are allowed.

Constraints

• 1 ≤ notes.size() ≤ 100,000
• 1 ≤ notes.get(i) ≤ 1,000,000,000
• 0 ≤ k ≤ 1,000,000,000

Examples

Example 1

minimumHandLifts( notes = List.of(2, 4, 6, 11, 8, 10), k = 4)

Output: 2

The first placement plays 2, 4, 6. Their extreme positions differ by 4. The hand is then repositioned to play 11, 8, 10, whose extreme positions differ by 3.

Example 2

minimumHandLifts( notes = List.of(8, 3, 7, 4), k = 5)

Output: 1

Every note can be reached from one placement covering positions 3 through 8.

Example 3

minimumHandLifts( notes = List.of(5, 5, 7, 7, 5), k = 0)

Output: 3

With a span of 0, one placement can cover only one position. The consecutive groups are 5, 5, 7, 7, and 5.

Example 4

minimumHandLifts( notes = List.of(10, 13, 9, 14, 18), k = 5)

Output: 2

One placement can play 10, 13, 9, 14 because the extreme positions differ by 5. A second placement is required for note 18.