← 返回题目列表

Codeforces · 670/B

B. 机器人游戏

中文机器翻译题面 查看原题

深秋的傍晚,n个机器人欢聚在朋友们的欢乐陪伴下。每个机器人都有一个唯一的标识符——一个 1 到 109 之间的整数。

在某个时刻,机器人决定玩“滚雪球”游戏。下面是这个游戏的规则。首先,所有机器人站成一排。然后第一个机器人说出了他的标识符。之后第二个机器人说出第一个机器人的标识符,然后说出他自己的标识符。然后第三个机器人说出第一个机器人的标识符,然后说出第二个机器人的标识符,最后说出他自己的标识符。这个过程从左到右继续,直到第 n 个机器人说出他的标识符。

您的任务是确定要发音的第 k 个标识符。

输入

第一行包含两个正整数 n 和 k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ min(2·109, n·(n + 1) / 2)。

第二行包含序列 id1, id2, ..., idn (1 ≤ idi ≤ 109) – 机器人的标识符。保证所有标识符都是不同的。

输出

打印第 k 个发音标识符(假设从 1 开始计数)。

示例

输入 #1

2 2
1 2

输出 #1

1

输入 #2

4 5
10 4 18 3

输出 #2

4

注意

在第一个示例中,机器人标识符将按以下顺序发音:1、1、2。当 k = 2 时,答案等于 1。

在第二个测试用例中,机器人的标识符将按以下顺序发音:10, 10, 4, 10, 4, 18, 10, 4, 18, 3。当 k = 5 时,答案等于 4。