Longest zigzag sales run: hints, no solution

A market stall records total sales for each day. You want to pick some days, keeping their order, whose sales zigzag: the step between the first two picked days goes strictly up or strictly down, and every later step goes the opposite way from the step before it. Picked days need not be adjacent, but two consecutively picked days must be at most maxGap positions apart, so picking day i and then day j needs j - i <= maxGap. Return the most days you can pick. One day alone is a zigzag of length 1, and an empty record gives 0.

Examples

Input

sales = [4, 9, 2, 7, 7, 3, 8], maxGap = 2

Output

6

Note

Pick 4, 9, 2, 7, 3, 8. Skipping the second 7 keeps every step within 2 days.

Input

sales = [5, 5, 5], maxGap = 3

Output

1

Note

Equal sales never form a step.

Input

sales = [1, 2, 3, 4], maxGap = 1

Output

2

Note

Only neighbours can be picked, so the steps cannot alternate for long.

Constraints

• 0 <= sales.length <= 2000
• -1000000 <= sales[i] <= 1000000
• 1 <= maxGap <= 2000

Hint 1: a nudge

Suppose you pick a day as the last one of your zigzag. What do you need to know about the previous pick to decide whether today can extend it?

Unlock the full hints and timed practice with a pass

The second and third hints and the timed, runner-checked practice are part of a pass.

See pricing