题目背景

小佳喜欢给数组排序。可惜他还不会高级排序算法。他心爱的冒泡排序玩腻了，于是他发明了一种排序，由于一交一替的很像波浪，便称它为“波浪排序”。他想知道给一个数组进行“波浪排序”需要多少次操作。

问题描述

给你一个长为 $n$ 的数组 $a_{1,2,...,n}$，进行若干回合操作将其排成升序。

对于每回合的操作：

• 第一步，对于每个奇数下标 $i$，将 $a_i$ 和 $a_{i+1}$ 排序，也就是说，如果 $a_i > a_{i+1}$ ，则交换 $a_i$ 和 $a_{i+1}$ 。
• 第二步，对于每个偶数下标 $i$，将 $a_i$ 和 $a_{i+1}$ 排序，同上。

对于i=n即i+1>n的，你应当忽略并不进行操作。

求总共（最少）需要的交换次数。

输入格式

共输入两行。

第一行一个正整数 $n$ ，表示数组元素个数。

第二行连续输入 $n$ 个正整数 $a_i$。

输出格式

一行一个正整数，表示“波浪排序”该数组需要的交换次数。

样例输入#1

5
2 4 1 3 5

样例输出#1

3

样例输入#2

5
1 2 3 4 5

样例输出#2

0

说明

对于第一组样例，

第一回合，第一步比较 $(a_1=2,a_2=4),2<4$ ，不交换，比较 $(a_3=1,a_4=3),1<3$，不交换；第二步比较 $(a_2=4,a_3=1),4>1$，交换，比较 $(a_4=3,a_5=5),3<5$ ，不交换。序列变为 $2\ 1\ 4\ 3\ 5$。

第二回合，第一步比较 $(a_1=2,a_2=1),2>1$ ，交换，比较 $(a_3=4,a_4=3),4>3$ ， 交换；序列变为 $1\ 2\ 3\ 4\ 5$ 已经有序了。

总操作次数为 $3$。

对于第二组样例，序列已经有序，故为 $0$。

评测数据规模

• 对于所有测试数据，保证 $n\le 2\times10^5$ ，$1\le a_i\le10^9$。