#ecnu20201A. 钥匙

钥匙

时间限制: 1.0 秒

空间限制: 256 MB

题目背景

经济危机席卷全球,L 国也收到冲击,大量人员失业。然而,作为 L 国的风云人物,X 找到了自己的新工作。从下周开始,X 将成为一个酒店的助理锁匠,当然,他得先向部门领导展示他的开锁能力。

领导给了 X 一串钥匙,这串钥匙串在一个大圆环上,每把钥匙有一个编号(1n1\sim n 之一),不同钥匙的编号不同。然后蒙上 X 的眼睛并把他带到一个圆形的大房间中。在这个房间中有 nn 个上锁的门,顺时针依次编号为 1n1\sim n。这 nn 把钥匙,刚好每一把对应打开一扇门(钥匙编号和门编号一致就可以将门打开)。X 的工作就是打开每扇门。

他因为蒙着眼睛的原因,只能从第 11 扇门开始,按顺时针方向,沿着房间的墙壁移动,中途不能改变方向。

当他摸到一扇门后,他会尝试用当前钥匙串中的第一把钥匙(最左边)来打开门,如果该钥匙不能将门打开,他会将该钥匙移到另外一侧(最右边),重复这样的过程,直到找到正确的钥匙将门打开为止,门打开后他就会继续朝下一扇门移动,他的任务是将所有的门都打开。注意,当一把钥匙将一扇门打开后,该钥匙仍然会保持在钥匙串的最左边,而不会被移到另外一侧(最右边)。

不过 X 不知道的是,领导并不是测试他开锁能力,而是测试他的耐心,所以 X 每开一扇门后,领导就会在后面悄悄把门再次锁上。这样一来,X 打开最后一扇门后又会回到第一扇门,然后一直重复下去。

不过 X 是一个勤奋和耐心的人,他一直毫无怨言的做着这件事,不说任何抱怨的话,只是在每开一扇门后,他都会默默的统计自己已经错误了多少次。

不过慢慢时间太久他的计算能力不足,需要你来帮助他计算错误的次数。

题目描述

给定数字 kk,请你计算从最开始到他第 kk 次打开一扇门为止,X 一共进行了多少次错误的开门尝试?

输入格式

从标准输入读入数据。

第一行包含 2 个整数 n,kn,k

接下来 nn 行,其中第 ii 行包含一个整数 viv_i,表示钥匙串中(左起)第 ii 把钥匙的编号。

输出格式

输出到标准输出。

一个整数,表示从最开始到他第 kk 次打开一扇门为止,X 一共进行的错误开门尝试次数。

4 6
4
2
1
3
13

样例 1 解释

开始尝试打开第 1 扇门(1 号门)时,钥匙排列:4 2 1 3,错误尝试 2 次后门被打开,打开后钥匙排列:1 3 4 2

开始尝试打开第 2 扇门(2 号门)时,钥匙排列:1 3 4 2,错误尝试 3 次后门被打开,打开后钥匙排列:2 1 3 4

开始尝试打开第 3 扇门(3 号门)时,钥匙排列:2 1 3 4,错误尝试 2 次后门被打开,打开后钥匙排列:3 4 2 1

开始尝试打开第 4 扇门(4 号门)时,钥匙排列:3 4 2 1,错误尝试 1 次后门被打开,打开后钥匙排列:4 2 1 3

开始尝试打开第 5 扇门(1 号门)时,钥匙排列:4 2 1 3,错误尝试 2 次后门被打开,打开后钥匙排列:1 3 4 2

开始尝试打开第 6 扇门(2 号门)时,钥匙排列:1 3 4 2,错误尝试 3 次后门被打开,打开后钥匙排列:2 1 3 4

一共错误尝试 13 次。

子任务

对于所有数据,1n105, 1k109, 1vin1\le n\le 10^5,~1\le k\le 10^9,~1\le v_i\le n