给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$ 和一个空的双端队列。

你需要按顺序将序列中的每一个数放进双端队列中，你可以选择将数插入到双端队列的队首或队尾。

你需要最小化最终得到的序列的逆序对数量。

输入格式

第一行一个整数 $n$ , 表示序列的长度。$(1 \leq n \leq 2 \times 10^5)$

第二行 $n$ 个数字 $a_1,a_2,\dots,a_n$ ，表示给定的序列。 $( -10^9 \leq a_i \leq 10^9 )$。

输出格式

输出一行一个整数，表示最少的逆序对数。

样例输入

4
3 7 5 5

样例输出

2