Amusement Park

Time limit2sMemory limit128 MB

Summary

Given ride durations and a queue of N children, find which numbered ride the last child in line boards, using binary search on time and counting boardings per ride.

Level: Medium7 of 10
Topics: Binary search, Math, Simulation, Implementation
Solved: No attempts yet

Problem

N children are waiting in one line for one-seat rides. The park has M rides numbered from 1 to M.

Each ride has a fixed duration. When that many minutes have passed, the child on the ride gets off and the ride immediately becomes empty. Whenever a ride is empty, the child at the front of the line boards it. If multiple rides become empty at the same time, children board them in increasing ride-number order.

Initially all rides are empty, and at minute 0 the first children board the available rides. Determine the number of the ride boarded by the last child in line.

Input

The first line contains the number of children N and the number of rides M, separated by a space. (1 <= N <= 2,000,000,000, 1 <= M <= 10,000)

The second line contains M natural numbers in order, where the ith number is the duration of ride i. Each duration is between 1 and 30 inclusive, and the unit is minutes.

Output

Print the number of the ride boarded by the last child.

Examples3

Example 1
Input
```
3 5
7 8 9 7 8
```
Expected output
```
3
```
Example 2
Input
```
7 2
3 2
```
Expected output
```
2
```
Example 3
Input
```
22 5
1 2 3 4 5
```
Expected output
```
4
```