Even-flow stretch: hints, no solution

A conveyor line tags each item passing a sensor with one of k SKUs, numbered 0 to k - 1. The sensor produces an event list where events[i] is the SKU of the i-th item.

A stretch is a contiguous part of the list. It is even-flow if every one of the k SKUs occurs the same number of times inside it. A SKU that does not appear counts zero, so the empty stretch is even-flow and the answer is 0 when nothing longer qualifies. When k is 1, any stretch qualifies. Return the length of the longest even-flow stretch.

Aim for one pass over the list whose cost grows linearly with the list length for a fixed k.

Examples

Input

events = [0, 1, 1, 0, 1], k = 2

Output

4

Note

The stretch [0, 1, 1, 0] holds two of each SKU; the whole list has 2 zeros and 3 ones.

Input

events = [1, 1, 1], k = 2

Output

0

Note

A stretch of only ones never contains a zero, so counts differ and only the empty stretch qualifies.

Input

events = [2, 0, 1, 0, 1, 2, 2, 1], k = 3

Output

6

Note

The first six items hold two of each of the three SKUs; the last two items would unbalance them.

Constraints

• 0 <= events.length <= 60000
• 1 <= k <= 10
• 0 <= events[i] < k
• The answer is the length of the stretch, 0 if none

Hint 1: a nudge

If you kept a running count of every SKU from the start, what would make a stretch between two positions even-flow?

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