Under construction

Still being built. Things may change

Round Trip

Interview

Time limit1sMemory limit256 MB

Summary
A runner travels out and back along N courses given by their lengths; given total distance K, print which course the runner is on or about to enter.
Level

Medium4 of 10

Topics
Array, Prefix sum, Binary search, Implementation
Solved
No attempts yet

Problem

A round-trip runner must pass through all N courses laid end to end on a straight line, reach the far end, and then return to the starting point. Given that the runner has covered distance K while traversing the courses, write a program that prints the number of the course the runner is currently on. If the distance K falls between two courses, print the number of the course the runner has yet to pass.

For example, let N=5 and the course lengths be 7, 4, 2, 4, 5 in order. Taking the starting point as 0, the layout of the courses can be drawn as follows.

  1. When K=0, the runner is on course 1, so print 1.
  2. When K=7, the runner is on course 2, so print 2.
  3. When K=9, the runner is on course 2, so print 2.
  4. When K=12, the runner is on course 3, so print 3.
  5. When K=28, this can be seen as the runner having reached the far end and returning to the starting position. The runner is on course 4, so print 4.

Also, K is always given as a positive integer smaller than the round-trip distance, or 0. For the example above, where the sum of all course lengths is 22, 0≤K≤43.

Input

The first line gives the integers N and K, separated by a space. (1≤N≤100,000) K is always a positive integer smaller than the round-trip distance, or 0. The second line gives the lengths of courses 1 through N in order, separated by spaces. Each course length is a natural number less than or equal to 50,000.

Output

On the first line, print the number of the course the runner is on when the distance covered is K.

Examples1

  1. Example 1

    Input
    5 28
    7 4 2 4 5
    
    Expected output
    4