Sasha 和 Dima 想买两个 $$$n$$$ 级蛋糕。每个蛋糕应由 $$$n$$$ 不同的层组成:从 $$$1$$$ 的大小到 $$$n$$$ 的大小。层应按从最小到最大(从上到下)的顺序排列。
他们住在同一条街上,从左到右有$$$2 \cdot n$$$ 房子。每栋房子都有一家糕点店,您可以在那里购买蛋糕层。不幸的是,在每家糕点店中,您只能购买一层特定尺寸的糕点:在第 $$$i$$$ 号房子中,您可以购买一层尺寸为 $$$a_i$$$ ($$$1 \le a_i \le n$$$) 的糕点。
由于这些家伙已经购买了层,并且不可能在蛋糕中间插入新层,因此他们同意从最小到最大购买层。也就是说,他们每个人都按顺序购买等级:$$$1$$$,然后是 $$$2$$$,然后是 $$$3$$$,依此类推,直到 $$$n$$$。
最初,Sasha 和 Dima 位于第一栋(最左边)房子附近。输出他们购买两个蛋糕总共需要步行的最短距离。任意两栋相邻房屋之间的距离恰好为 $$$1$$$。
输入
输入的第一行包含一个整数 $$$n$$$ — 每个蛋糕的层数 ($$$1 \le n \le 10^5$$$)。
第二行包含 $$$2 \cdot n$$$ 整数 $$$a_1, a_2, \dots, a_{2n}$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 等于层的大小,可以在第 $$$i$$$ 房子中购买。请记住,每栋房子只能购买一层。保证从 $$$1$$$ 到 $$$n$$$ 的每个数字在 $$$a$$$ 中恰好出现两次。
输出
打印一个数字——这些人购买两块蛋糕总共需要步行的最短距离。人们可以同时在同一所房子附近。他们从第一座(最左边的)房子附近开始。每个人都应该按尺寸升序购买 $$$n$$$ 层。
示例
输入 #1
3 1 1 2 2 3 3
输出 #1
9
输入 #2
2 2 1 1 2
输出 #2
5
输入 #3
4 4 1 3 2 2 3 1 4
输出 #3
17
注意
在第一个示例中,可能的最佳操作顺序是:
- Sasha 在 $$$1$$$-st 房子附近购买了一层大小为 $$$1$$$ 的房子 ($$$a_1=1$$$);
- 迪玛去房子$$$2$$$;
- Dima 在 $$$2$$$-nd 房子附近购买了一层大小为 $$$1$$$ 的房子 ($$$a_2=1$$$);
- 萨莎去房子$$$4$$$;
- Sasha 在第 $$$4$$$ 房子附近购买了一层大小为 $$$2$$$ 的房子 ($$$a_4=2$$$);
- 萨莎去房子$$$5$$$;
- Sasha 在第 $$$5$$$ 房子附近购买了一层大小为 $$$3$$$ 的房子 ($$$a_5=3$$$);
- 迪玛去房子$$$3$$$;
- Dima 在 $$$3$$$-rd 房子附近购买了一层大小为 $$$2$$$ 的房子 ($$$a_3=2$$$);
- 迪玛去房子$$$6$$$;
- Dima 在第 $$$6$$$ 号房子附近购买了一层尺寸为 $$$3$$$ 的房子 ($$$a_6=3$$$)。
所以,Sasha 走了 $$$3+1=4$$$ 距离,Dima 走了 $$$1+1+3=5$$$ 距离。他们总共行走的距离为$$$4+5=9$$$。您可以确保通过任何其他操作序列,他们行走的距离不会减少。