Перестановка — это последовательность из \(n\) целых чисел от \(1\) до \(n\), в которой все числа встречаются ровно по одному разу. Например, \([1]\), \([3, 5, 2, 1, 4]\), \([1, 3, 2]\) — перестановки, а \([2, 3, 2]\), \([4, 3, 1]\), \([0]\) — нет.
Поликарпу подарили перестановку \(p\) чисел от \(1\) до \(n\). Однако, когда Поликарп пришёл домой, он заметил, что в кармане перестановка \(p\) превратилась в массив \(q\) согласно следующему правилу:
- \(q_i = \max(p_1, p_2, \ldots, p_i)\).
Теперь Поликарпу стало интересно: какую лексикографически минимальную и лексикографически максимальную перестановки ему могли подарить.
Массив \(a\) длины \(n\) лексикографически меньше массива \(b\) длины \(n\), если существует индекс \(i\) (\(1 \le i \le n\)), такой что первые \(i-1\) элементов у массивов \(a\) и \(b\) совпадают, а \(i\)-й элемент у массива \(a\) меньше, чем \(i\)-й элемент у массива \(b\). Например массив \(a=[1, 3, 2, 3]\) лексикографически меньше массива \(b=[1, 3, 4, 2]\).
Например, если \(n=7\) и \(p=[3, 2, 4, 1, 7, 5, 6]\), тогда \(q=[3, 3, 4, 4, 7, 7, 7]\) и следующие перестановки могли быть в качестве \(p\) изначально:
- \([3, 1, 4, 2, 7, 5, 6]\) (лексикографически минимальная перестановка);
- \([3, 1, 4, 2, 7, 6, 5]\);
- \([3, 2, 4, 1, 7, 5, 6]\);
- \([3, 2, 4, 1, 7, 6, 5]\) (лексикографически максимальная перестановка).
Для заданного массива \(q\) найдите лексикографически минимальную и лексикографически максимальную перестановки, которые могли быть подарены Поликарпу изначально.