Пограничные врата
Contest: VK Cup 2018 - Квалификация 2
Difficulty rating: 2400

Герой Аркадий находится на узкой полоске земли, разделенной на n зон, пронумерованных от 1 до n. Из i-й зоны можно пройти лишь в (i - 1)-ю зону и в (i + 1)-ю зону, если они существуют. При этом между каждой парой соседних зон находятся пограничные врата, которые могут быть разных цветов, цвет врат между i-й и (i + 1)-й зоной равен gi.

Аркадий может пройти пограничные врата некоторого цвета, только если он перед этим побывал в одном из шатров хранителей ключей этого цвета и взял ключ. В каждой зоне находится ровно один шатер хранителя ключей некоторого цвета, цвет шатра в i-й зоне равен ki. После посещения шатра определенного цвета Аркадий может неограниченное число раз проходить через любые врата этого цвета.

На проход через одни врата Аркадий тратит один ход, на посещение шатра и другие перемещения ходы не требуются. За какое минимальное число ходов Аркадий может попасть из зоны a в зону b, если изначально у него нет никаких ключей?

Input format:
Первая строка содержит три целых числа n, a, b (2 ≤ n ≤ 100 000, 1 ≤ a, b ≤ n, a ≠ b) — число зон, номер начальной зоны и номер конечной зоны, соответственно.

Вторая строка содержит n - 1 целое число g1, g2, ..., gn - 1 (1 ≤ gi ≤ 100 000), где gi означает цвет пограничных врат между зонами i и i + 1.

Третья строка содержит n целых чисел k1, k2, ..., kn (1 ≤ ki ≤ 100 000), где ki означает цвет шатра хранителя ключей в i-й зоне.

Output format:
Если Аркадий не может попасть из зоны a в зону b, не имея изначально ключей, выведите -1.

Иначе выведите минимальное количество ходов, которое потребуется Аркадию.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
В первом примере, чтобы попасть из зоны 4 в зону 1, Аркадию нужно сначала взять ключ цвета 1, пройти в зону 3, там взять ключ цвета 2 и пройти обратно в зону 4 и затем в зону 5, взять там ключ цвета 3 и дойти до зоны 1 за четыре хода.

Во втором примере Аркадий может дойти лишь до четвертой зоны, так как шатров хранителей ключей цвета 1 нет совсем.

Example input:
5 4 1
3 1 1 2
7 1 2 1 3

Example output:
7

Example input:
5 1 5
4 3 2 1
4 3 2 5 5

Example output:
-1

Editorial:
Во-первых, для удобства, если a < b, то развернем все зоны и поменяем соответствующим образом a и b так, чтобы выполнялось a > b.
Теперь понятно, что Аркадию надо все время идти налево (уменьшая номер зоны) до зоны b, иногда при необходимости возвращаясь направо, правее зоны a, за необходимыми ключами. При этом, чтобы пройти некоторые врата правее зоны a, необходимо сначала пройти за ключом в некоторые зоны левее a. Поэтому задача определения, в какие моменты времени и насколько далеко нужно ходить направо, не является тривиальной.
Пройдем из зоны a в зону b, поддерживая набор ключей, которые у нас есть в данный момент. Кроме того, будем поддерживать, насколько далеко мы когда либо ходили вправо, пусть r — самый правый номер зоны, где мы когда-либо были. Пусть мы сейчас хотим перейти из зоны l в зону l - 1. Если перед нами врата, ключа от которых у нас нет, будем увеличивать r до тех пор, пока не найдем подходящий ключ. Если же в какой-то момент мы не сможем изменить ни l, ни r, потому что с обоих сторон врата, от которых у нас нет ключей, то, очевидно, Аркадий не сможет добраться до зоны b. В противном случае для каждой позиции l мы можем легко вычислить самую правую позицию r, которую нам надо посетить до перехода в зону l - 1. В то же время, для каждой такой правой позиции r мы можем легко вычислить самую левую позицию l', которую необходимо посетить для прохода в зону r. Очевидно, l' ≥ l, иначе ответ -1. Теперь по тройкам (l, r, l') необходимо посчитать минимальную длину пути, удовлетворяющую всем тройками.
Воспользуемся методом динамического программирования. Пусть dp[i][j] — минимальное число ходов, необходимое, чтобы оказаться в точке li, при этом последние перемещения были lj' → ri → li. Отметим, что в данном случае должно выполняться lk' ≥ lj' для всех j ≤ k ≤ i, иначе такое положение невозможно. Тогда, если li + 1' ≥ lj, то dp[i + 1][j] = dp[i][j] + (li - li + 1) + 2·(ri + 1 - ri): мы можем «продлить» последний поход вправо до положения ri + 1. Кроме того, всегда можно сначала дойти до точки li + 1', затем до ri и снова до li, тогда переход динамического программирования ведет в dp[i + 1][i + 1]. Конечным ответом будет минимальная из величин dp[k][t] + (lk - b), где k — количество троек, а 1 ≤ t ≤ k. Мы получили решение за O(n2), так как максимальное количество троек имеет порядок n, что является слишком медленным для полного решения.
Для полного решения задачи необходимо так же заметить, что dp[i + 1][j] - dp[i][j] не зависит от величины j для всех j < i + 1, поэтому все такие преобразования можно учитывать, не храня двумерный массив dp[i][j], а поддерживая только один массив dp'[j] и некоторую величину add, и считая, что dp[i][j] = dp'[j] + add, где i — текущая рассматриваемая тройка. Ограничения на lk' ≥ lj' можно учитывать, поддерживая минимальный j0 для которого это все еще выполняется. Кроме того, легко заметить, что среди всех доступных j минимальная величина dp[i][j] равна dp[i][j0]. Такие замечания позволяют реализовать вышеописанной метод динамического программирования за O(n) времени и памяти и получить полное решение.