670B.md (1762B)
1 Source: https://codeforces.com/problemset/problem/670/B 2 3 B. Game of Robots 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 In late autumn evening *n* robots gathered in the cheerful company of friends. Each robot has a unique identifier — an integer from 1 to 109. 22 23 At some moment, robots decided to play the game "Snowball". Below there are the rules of this game. First, all robots stand in a row. Then the first robot says his identifier. After that the second robot says the identifier of the first robot and then says his own identifier. Then the third robot says the identifier of the first robot, then says the identifier of the second robot and after that says his own. This process continues from left to right until the *n*-th robot says his identifier. 24 25 Your task is to determine the *k*-th identifier to be pronounced. 26 27 Input 28 29 The first line contains two positive integers *n* and *k* (1 ≤ *n* ≤ 100 000, 1 ≤ *k* ≤ *min*(2·109, *n*·(*n* + 1) / 2). 30 31 The second line contains the sequence *id*1, *id*2, ..., *id**n* (1 ≤ *id**i* ≤ 109) — identifiers of roborts. It is guaranteed that all identifiers are different. 32 33 Output 34 35 Print the *k*-th pronounced identifier (assume that the numeration starts from 1). 36 37 Examples 38 39 Input 40 41 ``` 42 2 2 43 1 2 44 ``` 45 46 Output 47 48 ``` 49 1 50 ``` 51 52 Input 53 54 ``` 55 4 5 56 10 4 18 3 57 ``` 58 59 Output 60 61 ``` 62 4 63 ``` 64 65 Note 66 67 In the first sample identifiers of robots will be pronounced in the following order: 1, 1, 2. As *k* = 2, the answer equals to 1. 68 69 In the second test case identifiers of robots will be pronounced in the following order: 10, 10, 4, 10, 4, 18, 10, 4, 18, 3. As *k* = 5, the answer equals to 4.