题目描述

在一个旧式火车站旁边有一座桥，桥面可以绕河中心的桥墩水平旋转。

这座桥最多只能容纳相邻的两节车厢。当桥旋转 $180^\circ$ 时，可以交换这两节相邻车厢的位置。

现在有 $N$ 节车厢，需要通过若干次这样的相邻交换，将所有车厢按照车厢号从小到大的顺序排列。

请计算最少需要进行多少次交换。

输入格式

第一行输入一个整数 $N$，表示车厢总数。

接下来输入 $N$ 个互不相同的整数，表示车厢初始排列的顺序。

这 $N$ 个整数之间以空白字符分隔，不保证全部位于同一行。

输出格式

输出一个整数，表示将车厢按照车厢号从小到大排列所需的最少交换次数。

样例

4
4 3 2 1

6

数据范围

$1 \le N \le 1000$。

所有车厢号互不相同。