luogu#P5552. Chino的试卷

Chino的试卷

题目背景

orz trz

Chino参加了萌妹子期末考试,又到了发试卷的时候了,但是,老师 yggygg 与 老师 ggyggy 就怎样发试卷才最省力这一事发生了一些争论。现在,为了解决这一矛盾,你决定帮Chino用数据说话。

下面是 yggygg 老师的发试卷策略,请你帮他计算发完试卷要走的总路程。

题目描述

为了简化问题,我们规定Chino的同学们(妹子们)都参加了考试,且坐在一排,顺次位置的编号为 1n1\sim n,不妨规定位置 ii, jj 之间的路程为 ij|i - j|。每张试卷上都有一个编号,代表要发给坐在这个编号的妹子。

yggygg 老师正在分发试卷。我们定义这个分发试卷的老师有两只手。刚开始,所有的试卷都在 yggygg 老师的左手,老师位于位置 ss 处。发试卷时,yggygg 老师会用右手拿起左手顶部的一张试卷。如果这是最后一张需要发的试卷,显然他别无选择,只能走到这张试卷主人的位置上去发这张试卷。如果他的左手还有试卷,那么他会进行一次比较,比较发左手顶部的那张试卷走的路程短,还是发右手那张试卷走的路程短。如果左手那张试卷走的路程短,他会把右手的试卷放到左手试卷的最下面,不然的话,他会直接发掉右手的试卷,并停留在刚发完这张试卷的位置。无论如何,他都会从左手再拿一张试卷,来进行下一步的决策,直到所有卷子都被发完。

现在,给定试卷的初始顺序序列pp,以及老师的初始位置 ss,问他要发完所有试卷走过的总路程是多少。

Chino想快速的知道答案,所以你要在+4s+4s内完成这道题哦qwq

Orz yky,dyh,wjk,jjy,cxr,gsy,cpy,zcy,tyz,yy,hz,zhr,ygg

输入格式

  • 第一行两个正整数 n,sn, s ,分别表示人数老师的初始位置。
  • 第二行 nn 个非负整数,其中第 ii 个数表示 pip_i ,即从上往下数第 ii 张试卷要发到哪里去。

输出格式

输出一个整数,表示需要走的总路程。

5 1
2 3 1 4 5
8

提示

测试点 n=n= 测试点 n=n =
1 3×1013\times10^1 11 3×1053\times10^5
2 3×1023\times10^2 12
3 13
4 3×1033\times10^3 14
5 15
6 16 3×1063\times10^6
7 3×1043\times10^4 17
8 18
9 19
10 20

对于前1515个测试点,时限1s1s

对于后55个测试点,时限4s4s