У вас есть массив \(a\) длины \(n\). Вы можете выполнять с ним следующую операцию:
- Выберите два индекса \(l\) и \(r\) такие, что \(1 \le l \le r \le n\) и \(a_l = a_r\). После этого разверните подотрезок с \(l\)-го по \(r\)-й элемент, то есть замените \([a_l, a_{l + 1}, \ldots, a_{r - 1}, a_r]\) на \([a_r, a_{r-1}, \ldots, a_{l+1}, a_l]\).
Вам также дан массив \(b\) длины \(n\), который является перестановкой \(a\). Найдите последовательность из не более чем \(n^2\) операций, которая превращает массив \(a\) в \(b\), или определите, что такого массива не существует.
Выходные данные
Для каждого набора входных данных выведите «NO» (без кавычек), если невозможно превратить \(a\) в \(b\), используя не более \(n^2\) операций.
Иначе выведите «YES» (без кавычек). Затем выведите целое число \(k\) (\(0 \leq k \leq n^2\)) — число операций, которое вы сделаете. Обратите внимание, что вам не нужно минимизировать число операций.
Затем выведите \(k\) строк. В \(i\)-й строке выведите два целых числа \(l_i\) и \(r_i\) (\(1 \leq l_i \leq r_i \leq n\)) — индексы для \(i\)-й операции.
Вы можете выводить «YES» и «NO» в любом регистре (например, строки «yEs», «yes» и «Yes» будут считаться положительным ответом).
Если существуют несколько решений, выведите любое из них.
Примечание
В первом примере можно выполнить следующие операции: \(\)[1,2,4,3,1,2,1,1] \xrightarrow[l=5,\,r=8]{} [1,2,4,3,1,1,2,1] \xrightarrow[l=1,\,r=6]{} [1,1,3,4,2,1,2,1].\(\)
Во втором примере можно выполнить следующие операции: \(\)[1,2,3,1,3,2,3] \xrightarrow[l=1,\,r=4]{} [1,3,2,1,3,2,3] \xrightarrow[l=3,\,r=6]{} [1,3,2,3,1,2,3].\(\)
Можно показать, что в третьем и четвертом примерах нельзя превратить \(a\) в \(b\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8
1 2 4 3 1 2 1 1
1 1 3 4 2 1 2 1
7
1 2 3 1 3 2 3
1 3 2 3 1 2 3
3
1 1 2
1 2 1
2
1 2
2 1
1
1
1
|
YES
2
5 8
1 6
YES
2
1 4
3 6
NO
NO
YES
0
|