Счастливый PMP учится в ВУЗе на первом курсе, где он изучает алгоритмические задачи. PMP обожает алгоритмические игры.
Один студент постарше дал счастливому PMP занятную игру. PMP даны две перестановки чисел от 1 до n, от него требуется преобразовать первую перестановку во вторую. За один шаг можно убрать из перестановки чисел последнее число и вставить его обратно в произвольное место. Другими словами, можно либо вставить последнее число между любыми двумя числами, идущими одно за другим, либо вставить число в начало перестановки.
Счастливый PMP знает алгоритм, решающий эту задачу, но он слишком медленный. PMP хочет знать минимальное количество шагов, за которое он может преобразовать первую перестановку во вторую.
Выходные данные
Выведите единственное целое число, обозначающее минимальное количество шагов, необходимых для преобразования первой перестановки во вторую.
Примечание
В первом примере PMP берет с конца списка число 1 и вставляет его в начало. Потом берет число 2 и вставляет его между 1 и 3.
Во втором примере он берет число 5 и вставляет его после 1.
В третьем примере последовательность шагов выглядит следующим образом:
- 1 5 2 3 4
- 1 4 5 2 3
- 1 3 4 5 2
- 1 2 3 4 5
Так что ему надо три хода.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2 1
1 2 3
|
2
|
|
2
|
5
1 2 3 4 5
1 5 2 3 4
|
1
|
|
3
|
5
1 5 2 3 4
1 2 3 4 5
|
3
|