Миссис Смит пытается связаться со своим мужем, мистером Смитом, но она забыла его секретный телефонный номер!
Единственное, что помнит миссис Смит, это то, что любая перестановка из \(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\).
Обратите внимание, что длины НВП и НУП могут быть различны.
Помогите, пожалуйста, миссис Смит найти перестановку, которая дает минимальную сумму длин НВП и НУП.
Примечание
В первом примере вы можете построить перестановку \([3, 4, 1, 2]\). НВП — \([3, 4]\) (или \([1, 2]\)), значит длина НВП равна \(2\). НУП может быть любой из \([3, 1]\), \([4, 2]\), \([3, 2]\) и \([4, 1]\). Длина НУП тоже равна \(2\). Сумма равна \(4\). Обратите внимание, что \([3, 4, 1, 2]\) не единственная перестановка, которая подходит.
Во втором примере вы можете построить перестановку \([2, 1]\). НВП — \([1]\) (или \([2]\)), значит длина НВП равна \(1\). НУП — \([2, 1]\), значит длина НУП равна \(2\). Сумма равна \(3\). Обратите внимание, что перестановка \([1, 2]\) тоже подходит.