E. Bashar and the bad land (Hard)
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The only difference between easy and hard versions is constraints.

Bashar is trapped in an abandoned city and he wants to escape. In order to escape, he has to pay $$$x$$$ golden coins. So he decided to collect the gold in the houses of that city. The city contains $$$n$$$ houses aligned in a straight line. Each house contains $$$a_i$$$ coins of gold.

Help Bashar to find the shortest distance he has to walk until he collects the needed amount of golden coins to get away.

Note Bashar can start from any house and stop at any house.

Input

First line of input contains two integers $$$x$$$, and $$$n$$$, $$$(1 \leq n \leq 10^{5} , 1\leq x \leq 10^{9})$$$ The needed amount of gold until Bashar can get away, and The number of houses in the city.

The second line of input contains $$$n$$$ integers $$$a_i$$$, $$$(1 \leq a_i \leq 10^{5})$$$ the amount of gold in the $$$i^{th}$$$ house.

Output

Print a single represents the minimum distance Bashar has to walk until he reach The needed amount of golden coins, if he can't reach The needed amount of golden coins print -1.

Examples
Input
5 12
1 3 4 5 2
Output
3
Input
5 13
5 1 2 3 4
Output
5
Input
5 6
1 1 1 1 1
Output
-1
Note

In the first example, Bashar walked from $$$2^{nd}$$$ house to the $$$4^{th}$$$ house to collect 12 coins (3+4+5=12), so the distance is 3.