Problem Statement

“时间飞快的流逝，唯独现在，我有一种想对爱因斯坦发牢骚的心情，Rintarou，时间根据每个人的主观感受，既会变长，也会变短，相对论真是既浪漫又伤感的东西呢。”

因为Kurisu是天才科学家、疯狂实验妹、重度的@Cher、天才**少女、The zombie，但是她并不中二，所以题面会比较清新。

Kurisu 正在研究相对论，你秒了上一题后 Kurisu 由于研究时不近人情与高傲的态度，想要出一道题来打击一下你。

题面如下：
小Rintarou正在研究交换。
小Rintarou认为一个整数序列是好的，当且仅当它先（不严格）上升，后（不严格）下降。
形式化地，我们认为序列\(a_1, a_2, · · ·, a_n\)是好的，当且仅当存在某个\(k ∈ [1, n]\)，使得对于任意\(1 ≤ i < k\)，有\(a_i ≤ a_{i+1}\)；且对于任意\(k ≤ i < n\)，有\(a_i ≥ a_{i+1}\)

小 Rintarou 得到了一个长度为\(n\)的序列\(a_1, a_2, · · ·, a_n\)，他想让这个序列变成好的。小 Rintarou 每次可以交换**相邻**的两个元素。因为交换很累，所以小 Rintarou 想知道，他最少需要交换多少次。

这下小 Rintarou 又不会了，请你帮帮他。

Input Format

从标准输入读入数据。
第一行一个正整数\(n\)，表示序列的长度。
第二行\(n\)个空格隔开的整数\(a_1, a_2, · · ·, a_n\)，表示初始的序列。

Output Format

向标准输出输出答案。
输出一行一个整数，表示最小交换次数。

Sample 1

Input

6
6 5 1 3 2 4

Output

4

Explanation

Kurisu 看你眉头紧皱，于是就过来帮帮你
一组最优解如下：

• 交换 \(a_5, a_6\)，得到\(a = [6, 5, 1, 3, 4, 2]\)；
• 交换 \(a_4, a_5\)，得到\(a = [6, 5, 1, 4, 3, 2]\)；
• 交换 \(a_2, a_3\)，得到\(a = [6, 1, 5, 4, 3, 2]\)；
• 交换 \(a_1, a_2\)，得到\(a = [1, 6, 5, 4, 3, 2]\)。

Constraints

对于所有测试数据\(1 ≤ n ≤ 3 × 10^5，1 ≤ a_i ≤ n\)

对于前10% 的数据\(n ≤ 10\)
对于前40% 的数据\(n ≤ 500\)
对于前60% 的数据\(n ≤ 100000\)
对于另外20% 的数据\(a\)为\([1,n]\)的一个排列
对于前100% 的数据 没有限制