Вы наверняка знаете, что такое перестановка, но на всякий случай, напомним:
Перестановкой из $$$n$$$ элементов называется последовательность $$$p_1, p_2, \dots, p_n$$$, в которой все числа от $$$1$$$ до $$$n$$$ встречаются один раз.
Для последовательности $$$a_1,a_2, \dots, a_n$$$ также определим количество инверсий как количество пар $$$i, j$$$ таких, что $$$i \lt j$$$ и $$$a_i \gt a_j$$$. Красотой последовательности длины $$$m$$$ назовем число $$$m$$$ минус количество инверсий в этой последовательности.
Вам дана перестановка из $$$n$$$ элементов. Разрешено вычеркнуть из нее любое количество чисел. Найдите, какую максимальную красоту последовательности можно получить.
В первой строке входного файла содержится одно целое число $$$n$$$ — количество элементов в перестановке.
Во второй строке содержатся $$$n$$$ разделенных пробелом целых чисел $$$p_1, p_2, \dots, p_n$$$ — исходная перестановка.
$$$$$$1 \le n \le 2 \cdot 10^5$$$$$$ $$$$$$ 1 \le p_i \le n$$$$$$
Все $$$p_i$$$ различны.
Выведите одно целое число — значение максимальной красоты, которую можно получить.
5 1 2 3 5 4
4
6 2 1 3 4 5 6
5
В первом тестовом примере подойдет последовательность «$$$1$$$ $$$2$$$ $$$3$$$ $$$4$$$» или «$$$1$$$ $$$2$$$ $$$3$$$ $$$5$$$», обе с красотой $$$4$$$.
Во втором тестовом примере можно взять всю последовательность «$$$2$$$ $$$1$$$ $$$3$$$ $$$4$$$ $$$5$$$ $$$6$$$» с красотой $$$5$$$.
