406411: GYM102397 E Bashar and the bad land (Hard)

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.

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.

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.

5 12
1 3 4 5 2

3

5 13
5 1 2 3 4

5

5 6
1 1 1 1 1

-1

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.