Дана перестановка \(a_1, a_2, \dots, a_n\) целых чисел от \(1\) до \(n\), и пороговое значение \(k\) такое, что \(0 \leq k \leq n\), по ним вычисляется последовательность \(b_1, b_2, \dots, b_n\) следующим образом.
Для всех \(1 \leq i \leq n\) в порядке возрастания положим \(x = a_i\).
- Если \(x \leq k\), приравняем \(b_{x}\) последнему элементу \(a_j\) (\(1 \leq j < i\)) такому, что \(a_j > k\). Если такого элемента \(a_j\) не существует, положим \(b_{x} = n+1\).
- Если \(x > k\), приравняем \(b_{x}\) последнему элементу \(a_j\) (\(1 \leq j < i\)) такому, что \(a_j \leq k\). Если такого элемента \(a_j\) не существует, положим \(b_{x} = 0\).
К сожалению, после построения последовательности \(b_1, b_2, \dots, b_n\), перестановка \(a_1, a_2, \dots, a_n\) и пороговое значение \(k\) потерялись.
Теперь у вас есть только последовательность \(b_1, b_2, \dots, b_n\). Ваша задача найти любую подходящую перестановку \(a_1, a_2, \dots, a_n\) и пороговое значение \(k\) которые порождают последовательность \(b_1, b_2, \dots, b_n\). Гарантируется, что существует хотя бы одна пара перестановки \(a_1, a_2, \dots, a_n\) и порогового значения \(k\), что порождают \(b_1, b_2, \dots, b_n\).
Перестановкой чисел от \(1\) до \(n\) называется последовательность длины \(n\) которая содержит все целые числа от \(1\) до \(n\) ровно один раз.
Выходные данные
Для каждого набора входных данных выведите пороговое значение \(k\) (\(0 \leq k \leq n\)) в первой строке, и затем выведите перестановку \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq n\)) во второй строке так, что перестановку \(a_1, a_2, \dots, a_n\) и пороговое значение \(k\) порождают последовательность \(b_1, b_2, \dots, b_n\). Если существуют несколько решений, выведите любое из них.
Примечание
В первом примере перестановка \(a = [1,3,2,4]\) и пороговое значение \(k = 2\) породят \(b\) следующим образом.
- Когда \(i = 1\), \(x = a_i = 1 \leq k\), нет такого \(a_j\) (\(1 \leq j < i\)) что \(a_j > k\). Значит, \(b_1 = n + 1 = 5\).
- Когда \(i = 2\), \(x = a_i = 3 > k\), последний элемент \(a_j\) такой, что \(a_j \leq k\) это \(a_1\). Значит, \(b_3 = a_1 = 1\).
- Когда \(i = 3\), \(x = a_i = 2 \leq k\), последний элемент \(a_j\) такой, что \(a_j > k\) это \(a_2\). Значит, \(b_2 = a_2 = 3\).
- Когда \(i = 4\), \(x = a_i = 4 > k\), последний элемент \(a_j\) такой, что \(a_j \leq k\) это \(a_3\). Значит, \(b_4 = a_3 = 2\).
Получается последовательность
\(b = [5,3,1,2]\).
Для второго примера перестановка \(a = [1,2,3,4,5,6]\) и пороговое значение \(k = 3\) породят \(b\) следующим образом.
- Когда \(i = 1, 2, 3\), \(a_i \leq k\), нет такого \(a_j\) (\(1 \leq j < i\)) что \(a_j > k\). Значит, \(b_1 = b_2 = b_3 = n + 1 = 7\).
- Когда \(i = 4, 5, 6\), \(a_i > k\), последний элемент \(a_j\) такой, что \(a_j \leq k\) это \(a_3\). Значит, \(b_4 = b_5 = b_6 = a_3 = 3\).
Получается последовательность
\(b = [7,7,7,3,3,3]\).
Для третьего примера перестановка \(a = [6,5,4,3,2,1]\) и пороговое значение \(k = 3\) породят \(b\) следующим образом.
- Когда \(i = 1, 2, 3\), \(a_i > k\), нет такого \(a_j\) (\(1 \leq j < i\)) что \(a_j \leq k\). Значит, \(b_4 = b_5 = b_6 = 0\).
- Когда \(i = 4, 5, 6\), \(a_i \leq k\), последний элемент \(a_j\) такой, что \(a_j > k\) это \(a_3\). Значит, \(b_1 = b_2 = b_3 = a_3 = 4\).
Получается последовательность
\(b = [4,4,4,0,0,0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
5 3 1 2
6
7 7 7 3 3 3
6
4 4 4 0 0 0
|
2
1 3 2 4
3
1 2 3 4 5 6
3
6 5 4 3 2 1
|