Миссис Смит пытается связаться со своим мужем, мистером Смитом, но она забыла его секретный телефонный номер!

Единственное, что помнит миссис Смит, это то, что любая перестановка из $$$n$$$ чисел может быть секретным номером телефона. Но только те перестановки, которые имеют минимальное секретное значение, могут быть номером телефона её мужа.

Последовательность из $$$n$$$ чисел называется перестановкой, если она содержит в себе все числа от $$$1$$$ до $$$n$$$ ровно по одному разу.

Секретным значением перестановки называется сумма длин наибольшей возрастающей подпоследовательности (НВП) и наибольшей убывающей подпоследовательности (НУП).

Подпоследовательность $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$, где $$$1\leq i_1 < i_2 < \ldots < i_k\leq n$$$ называется возрастающей, если $$$a_{i_1} < a_{i_2} < a_{i_3} < \ldots < a_{i_k}$$$. Если $$$a_{i_1} > a_{i_2} > a_{i_3} > \ldots > a_{i_k}$$$, то подпоследовательность называется убывающей. Возрастающая/убывающая подпоследовательность называется наибольшей, если она обладает максимальной длиной среди всех возрастающих/убывающих подпоследовательностей.

Например, если есть перестановка $$$[6, 4, 1, 7, 2, 3, 5]$$$, НВП этой перестановки будет $$$[1, 2, 3, 5]$$$, а длина НВП будет $$$4$$$. НУП может быть $$$[6, 4, 1]$$$, $$$[6, 4, 2]$$$ или $$$[6, 4, 3]$$$, значит длина НУП равна $$$3$$$.

Обратите внимание, что длины НВП и НУП могут быть различны.

Помогите, пожалуйста, миссис Смит найти перестановку, которая дает минимальную сумму длин НВП и НУП.