Создайте перестановку длины N, имеющую LIS одинакового размера с обоих концов

По заданному целому N задача состоит в том, чтобы сгенерировать перестановку элементов в диапазоне [1, N] в таком порядке, чтобы длина LISfrom start была равна LIS начиная с конца массива. Выведите -1, если такого массива не существует.

Примеры:

Input: N = 5
Output: [1, 3, 5, 4, 2]
Explanation:
LIS from left side: [1, 3, 5] 
LIS from right side: [2, 4, 5] 
Length of LIS from left and right side is same that is 3.

Input: N = 7
Output: [1, 3, 4, 7, 6, 5, 2]
Explanation:
LIS from left side: [1, 3, 4, 7]
LIS from right side: [2, 5, 6, 7]
Length of LIS from left and right side is same that is 4.

Подход: используйте следующее наблюдение, чтобы решить эту проблему:

• If N = 2, then such an array doesn’t exist.
• Else if N is odd,
  • Then start by adding 1 at index 0 and adding 2 at index N-1.
  • Now, add N at index N/2. After that, if N>3 then add remaining numbers 3, 4, 5, ... so on indices 1, 2, …, (N/2-1).
  • Now add remaining numbers in decreasing order from index N/2+1 to N-2.
• If N is even,
  • say 4 then it has only 1 possible solution: {2, 1, 4, 3}.
  • After 4, suppose N = 6, then just add 6 at starting and 5 at ending to the previous answer for N = 4 which forms array = [6, 2, 1, 4, 3, 5].
  • Similarly, for next even N just add N at 0th index and N-1 at last index..

Выполните шаги, указанные ниже, чтобы решить проблему:

• Если указанный размер равен 2, верните -1.
• В противном случае добавьте элементы в соответствии с упомянутым выше наблюдением.
• Вернуть сформированный список и вывести элементы списка.

Ниже приведена реализация вышеуказанного подхода:

Сложность времени: НА)
Вспомогательное пространство: O(N)