Full tariff coverage: hints, no solution

A billing system receives a stream of tariff codes, one per metered hour, as integers. An auditor keeps a list of required codes, and a window is any run of consecutive entries of the stream, of any length, that contains every required code at least once. The required list may repeat a code, which does not change what is required.

Count the windows that cover all required codes. Windows are counted by position, so equal-looking runs at different places count separately. Other codes may appear inside a window freely. If some required code never occurs in the stream, the answer is 0.

Examples

Input

codes = [1, 2, 3, 1, 2], required = [1, 2]

Output

8

Note

Eight windows hold both 1 and 2, for example positions 0 to 1 and positions 3 to 4.

Input

codes = [4, 5, 6], required = [9]

Output

0

Note

Code 9 never occurs, so no window can cover it.

Input

codes = [3, 3, 5, 5], required = [5, 5, 3]

Output

4

Note

Repeated required codes are still one requirement.

Constraints

• 0 <= codes.length <= 90000
• 1 <= codes[i] <= 100000
• 1 <= required.length <= 20, values in the same range

Hint 1: a nudge

Suppose a window ending at some position covers everything. What can you say about windows that start earlier but end at the same position?

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