Description

恶魔猎手的部队气势汹汹的开赴到了兽族阵前。
恶魔猎手：愚蠢的先知，给我出来！
先知：来者何人，敢在本先知大人面前叫嚣？
恶魔猎手：既然你诚心诚意的发问了，我就大发慈悲的告诉你！为了防止世界被破坏；为了维护世界的和平！贯彻爱与真实的邪恶；可爱又迷人的反派角色~我就是恶魔猎手――尤迪安.暴风!!
先知：￥@%&@~#！
......
于是精灵族和兽族正式开打了，但是姜还是老的辣，恶魔猎手到底太年轻了，经验不够，精灵族伤亡惨重，于是恶魔猎手带领部队撤退了。
撤退途中，由于恶魔猎手的部队被兽族冲击的七零八落，所以撤退速度特别慢，为了加快行进速度，恶魔猎手决定先停下来整一下队伍。
假设所有人都在一条直线上，每个人都有一个编号，当他们的编号是按从小到大排列的时候，行进速度最快。恶魔猎手整队的过程是这样的，每次选相邻的两个人交换一下位置，头跟尾不相邻。问最少需要交换多少次才能保证所有人的编号都是从小到大的。

Input

每组两行。
第一行一个整数n(1<=n<=100000)，第二行n个整数(每个数大于等于1，小于等于n)，表示每个人的编号。

Output

输出最少需要交换的次数。

Sample Input

1
1
2
2 1
3
3 2 1
4
3 2 4 1
5
5 3 1 2 4
6
5 2 4 1 3 6
7
3 4 1 6 2 7 5

Sample Output

0
1
3
4
6
7
7

HINT

Source

NBU OJ