Sentry Checkpoint Gap

A night-shift sentry walks a fixed patrol loop and, at every step, radios back the label of whichever checkpoint they are currently standing at, building up a log of n checkpoint labels in visiting order (the sentry revisits many checkpoints many times over the course of the patrol). Security wants to know how tightly two particular checkpoints are interleaved in that log: given two distinct checkpoint labels that are each guaranteed to appear somewhere in the log, find the fewest number of steps between some visit to the first checkpoint and some visit to the second checkpoint — that is, the minimum value of |i − j| over every step index i at which the first label was radioed and every step index j at which the second label was radioed.

Input format

Line 1: a single integer n, the number of logged steps. Line 2: n space-separated lowercase strings, the checkpoint label radioed at each step, in order. Line 3: two space-separated lowercase strings w1 and w2, the two checkpoint labels to compare (w1 ≠ w2).

Output format

A single integer: the minimum step distance between any occurrence of w1 and any occurrence of w2 in the log.

Constraints

• 2 ≤ n ≤ 10^5
• each logged label and each of w1, w2 consists of 1 to 20 lowercase English letters
• w1 and w2 are distinct, and each occurs at least once in the log

5
alpha bravo charlie delta bravo
delta alpha

3

6
north south north east north south
north east

1