The only difference between easy and hard versions is constraints.

Ivan plays a computer game that contains some microtransactions to make characters look cooler. Since Ivan wants his character to be really cool, he wants to use some of these microtransactions — and he won't start playing until he gets all of them.

Each day (during the morning) Ivan earns exactly one burle.

There are $n$ types of microtransactions in the game. Each microtransaction costs $2$ burles usually and $1$ burle if it is on sale. Ivan has to order exactly $k_i$ microtransactions of the $i$-th type (he orders microtransactions during the evening).

Ivan can order any (possibly zero) number of microtransactions of any types during any day (of course, if he has enough money to do it). If the microtransaction he wants to order is on sale then he can buy it for $1$ burle and otherwise he can buy it for $2$ burles.

There are also $m$ special offers in the game shop. The $j$-th offer $(d_j, t_j)$ means that microtransactions of the $t_j$-th type are on sale during the $d_j$-th day.

Ivan wants to order all microtransactions as soon as possible. Your task is to calculate the minimum day when he can buy all microtransactions he want and actually start playing.


-----Input-----

The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of types of microtransactions and the number of special offers in the game shop.

The second line of the input contains $n$ integers $k_1, k_2, \dots, k_n$ ($0 \le k_i \le 2 \cdot 10^5$), where $k_i$ is the number of copies of microtransaction of the $i$-th type Ivan has to order. It is guaranteed that sum of all $k_i$ is not less than $1$ and not greater than $2 \cdot 10^5$.

The next $m$ lines contain special offers. The $j$-th of these lines contains the $j$-th special offer. It is given as a pair of integers $(d_j, t_j)$ ($1 \le d_j \le 2 \cdot 10^5, 1 \le t_j \le n$) and means that microtransactions of the $t_j$-th type are on sale during the $d_j$-th day.


-----Output-----

Print one integer — the minimum day when Ivan can order all microtransactions he wants and actually start playing.


-----Examples-----
Input
5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3

Output
8

Input
5 3
4 2 1 3 2
3 5
4 2
2 5

Output
20

Difficulty: introductory

Starter code:

Solutions:
import collections


def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    def enough(days):
        bought = []  # (type, amount)
        bought_total = 0
        used_from = days
        for d in range(days, 0, -1):
            used_from = min(d, used_from)
            for t in offers.get(d, []):
                if K[t] > 0:
                    x = min(K[t], used_from)
                    K[t] -= x
                    bought.append((t, x))
                    bought_total += x
                    used_from -= x
            if not used_from:
                break
        remaining_money = days - bought_total
        ans = (total_transaction - bought_total) * 2 <= remaining_money
        for t, a in bought:
            K[t] += a
        return ans

    n, m = read_int_array()
    K = read_int_array()
    total_transaction = sum(K)
    offers = collections.defaultdict(list)
    for _ in range(m):
        d, t = read_int_array()
        offers[d].append(t-1)

    low = total_transaction
    high = low * 2
    ans = high
    while low <= high:
        mid = (low + high) // 2
        if enough(mid):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    write(ans)


main()


import sys

N, M = [int(x) for x in sys.stdin.readline().rstrip().split()]
K = [int(x) for x in sys.stdin.readline().rstrip().split()]
D = [0]*M
T = [0]*M
for i in range(M):
    D[i], T[i] = [int(x) for x in sys.stdin.readline().rstrip().split()]
    D[i] -= 1
    T[i] -= 1
KS = sum(K)

ok = 2*KS
ng = KS-1
while ok - ng > 1:
    X = (ok+ng) // 2
    last = [-1]*N
    for i in range(M):
        if last[T[i]] < D[i] < X:
            last[T[i]] = D[i]
    l2i = [[] for i in range(X)]
    for i in range(N):
        if last[i] != -1:
            l2i[last[i]].append(i)
    
    buy = 0
    now = 0
    for i in range(X):
        now += 1
        for j in l2i[i]:
            s = now if now < K[j] else K[j]
            now -= s
            buy += s
    buy += now // 2

    if buy >= KS:
        ok = X
    else:
        ng = X

print(ok)


import sys

def main():
    n, m = map(int, input().split())
    k = [int(x) for x in input().split()]

    d = [[] for _ in range(4 * 10**5 + 1)]
    for j in range(m):
        dj, tj = map(int, input().split())
        d[dj - 1].append(tj - 1)

    lo, hi = 0, 4 * 10**5 + 1
    while lo < hi:
        mi = (hi + lo) // 2
        cash = mi
        offset = 0

        _k = k[:]
        for i in reversed(range(mi)):
            for j in d[i]:
                while cash and _k[j]:
                    _k[j] -= 1
                    cash -= 1
            if cash == i + 1:
                cash -= 2
                offset += 1

        if 2 * (sum(_k) - offset) <= cash:
            hi = mi
        else:
            lo = mi + 1

    print(lo)

input = iter(sys.stdin.read().splitlines()).__next__

def __starting_point():
    main()
__starting_point()

import sys
import bisect
import copy
input = sys.stdin.readline

n,m=list(map(int,input().split()))
K=[0]+list(map(int,input().split()))
SP=[list(map(int,input().split())) for i in range(m)]

SP2=[[] for i in range(n+1)]

for d,t in SP:
    SP2[t].append(d)

for i in range(n+1):
    SP2[i].sort()

SUM=sum(K)
MIN=SUM
MAX=SUM*2
MAXBUY=0

while MIN!=MAX:
    day=(MIN+MAX)//2

    DAYS=[[] for i in range(day+1)]

    for i in range(n+1):
        x=bisect.bisect_right(SP2[i],day)-1
        if x>=0:
            DAYS[SP2[i][x]].append(i)

    GOLD=0
    SUMK=SUM
    K2=copy.deepcopy(K)

    for d in range(1,day+1):
        GOLD+=1

        for t in DAYS[d]:
            DBUY=min(K2[t],GOLD,SUMK)
            K2[t]-=DBUY
            GOLD-=DBUY


    if GOLD>=sum(K2)*2:
        MAX=day
    else:
        MIN=day+1

print(MIN)




        
        


import math
from collections import defaultdict
import sys
#input = sys.stdin.readline


def main():
    n, m = list(map(int, input().split()))
    k = list(map(int, input().split()))
    sales = [(0, 0)] * m
    for i in range(m):
        a, b = list(map(int, input().split()))
        sales[i] = (b, a)

    def check(days):
        last_sale = {}
        for sale in sales:
            if sale[1] <= days:
                if sale[0] not in last_sale or sale[1] > last_sale[sale[0]]:
                    last_sale[sale[0]] = sale[1]

        date_last_sales = {}
        for t, d in list(last_sale.items()):
            if d not in date_last_sales:
                date_last_sales[d] = [t]
            else:
                date_last_sales[d].append(t)

        balance = 0
        required = [0] + k.copy()

        end = 0
        for d in range(1, days+1):
            balance += 1
            if d in date_last_sales:
                for t in date_last_sales[d]:
                    if required[t] > 0:
                        if required[t] > balance:
                            end += required[t] - balance
                        balance -= min(required[t], balance)
                        required[t] = 0
            if d == days:  # last day
                for r in required:
                    if r > 0:
                        end += r

        return 2*end <= balance

    total = sum(k)
    hi = 2*total
    lo = 1

    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid

    if check(lo):
        print(lo)
    else:
        print(hi)


def __starting_point():
    main()

__starting_point()

import sys
import copy

DEBUG = False

if DEBUG:
    inf = open("input.txt")
else:
    inf = sys.stdin

N, M = list(map(int, inf.readline().split(' ')))
n_items = list(map(int, inf.readline().split(' ')))
sales = []
for _ in range(M):
    sale = list(map(int, inf.readline().split(' ')))
    sales.append(sale) # sale_day, sale_type

sales = sorted(sales, key=lambda x: x[0], reverse=True) # sort by day

def can_buy_in(dday):
    used = 0
    money_left = dday
    items = n_items[:]
    for sale_day, sale_type in sales:
        if sale_day > dday:
            continue
        
        if money_left > sale_day:
            money_left = sale_day
        can_buy = min(items[sale_type-1], money_left)
        # buy it
        used += can_buy
        items[sale_type-1] -= can_buy
        money_left -= can_buy

        if money_left == 0:
            break
    
    need_money_for_rest = sum(items) * 2
    return need_money_for_rest + used <= dday

total_items = sum(n_items)
low = total_items
high = total_items * 2

# find minimum can_buy day
while low <= high:
    mid = (low + high) // 2
    if can_buy_in(mid):
        high = mid-1
    else:
        low = mid+1

print(low)

#binary search reconstructure
  

def BinarySearch(my_list,key):
    l = 0
    r = len(my_list)- 1 
    #print(l,r)
    while r > l :
        mid = (l+r)//2
        if my_list[mid+1] <= key :
            l = mid + 1  
        else :
            r = mid   
        #print(l,r)
    return l

def weather_can_buy(day,total,req_list,sale_days):
    tmp_buy = []
    last_day = []
    # money = day
    # bug anything that is on sale
    d = day
    my_total = total
    for i in range(len(req_list)) : 
        last_day.append(0)
    for i in range(d):
        tmp_buy.append(0)    
    for i in range(len(sale_days)) : 
        if len(sale_days[i]) > 0 : 
            index = BinarySearch(sale_days[i],day)
            last_day[i] = sale_days[i][index]
    for i in range(len(last_day)) :
        if last_day[i]-1 > -1 :
            tmp_buy[last_day[i]-1] += req_list[i]
    # buying
    money = 0
    for i in range(d):
        money += 1
        my_total -= min(money,tmp_buy[i])
        money -= min(money,tmp_buy[i])        
    if my_total < 0 :
        return True
    elif money >= my_total * 2:
        return True
    else :
        return False
    
def function():
    tmp = input().split(" ")
    n = int(tmp[0]) # The number of type
    m = int(tmp[1]) 
    req_list = input().split(" ")
    req_list = list(map(int,req_list)) 
    total = sum(req_list)
    sale_days = []
    # sale days for acceleration
    for i in range(len(req_list)):
        sale_days.append([0])  
    for i in range(m) :
        tmp = input().split(" ")
        dj,tj = (int(tmp[0]),int(tmp[1]))
        sale_days[tj-1].append(dj)
    for i in range(len(sale_days)) :
        sale_days[i] = sorted(sale_days[i])
    # optimized by sorting
    for i in range(len(sale_days)) :
        sale_days[i] = sorted(sale_days[i])     
    #day = 0

    l = 1
    r = 2*total
    while r > l :
        mid = (l+r)//2
        if weather_can_buy(mid,total,req_list,sale_days) :
            r = mid
        else :
            l = mid + 1 
    print(r)
    
function()


def check(mid):
	l = [0 for i in range(n)]
	for i in b:
		if(i[0] > mid): break
		l[i[1]-1] = i[0]
	v = [0 for i in range(mid+1)]
	for i in range(n):
		v[l[i]] += a[i]
	ct = 0
	for i in range(1,mid+1):
		ct += 1
		if(ct >= v[i]):
			ct -= v[i]
			v[i] = 0
		else:
			v[i] -= ct
			ct = 0
	return ct >= 2*sum(v)

def bs():
	l = 0
	r = 5*10**5
	while(l <= r):
		mid = (l+r)//2
		if(check(mid)):
			r = mid-1
		else:
			l = mid+1
	return r+1

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = []
for i in range(m):
	b.append(list(map(int,input().split())))
b.sort()
print(bs())

import sys
input = sys.stdin.readline
def check(num):
	last = [0 for i in range(n)]
	for i in o:
		if i[0]>num:
			break
		else:
			last[i[1]-1] = i[0]
	b = [0 for i in range(num+1)]
	for i in range(n):
		b[last[i]] += a[i]

	i = 0
	c = 0
	d = 0
	for i in range(1,num+1):
		c += 1
		if(c >= b[i]):
			c -= b[i]
			b[i] = 0
		else:
			b[i] -= c
			c = 0

	s = sum(b)
	if s*2<=c:
		return True
	return False



n,m = map(int,input().split())
a = list(map(int,input().split()))
o = []
for i in range(m):
	x,y = map(int,input().split())
	o.append((x,y))
o.sort()
low = 1
high = sum(a)*2
while low<high:
	mid = (low+high)//2
	if check(mid):
		high = mid - 1
	else:
		low = mid + 1
if check(low):
	print (low)
else:
	print (low+1)

def check(x):
    last=[0]*(n+1)
    for i in tmp:
        if i[0]>x:
            break
        else:
            last[i[1]]=i[0]
    sal=[0]*(x+1)
    for i in range(1,n+1):
        sal[last[i]]+=lis[i-1]
    c=0
    for i in range(1,x+1):
        c+=1
        if sal[i]>=c:
            sal[i]-=c
            c=0
        else:
            c-=sal[i]
            sal[i]=0
    if sum(sal)*2<=c:
        return True
    else:
        return False        
n,m = list(map(int,input().split()))
lis = list(map(int,input().split()))
tmp=[]
for _ in range(m):
    a,b = list(map(int,input().split()))
    tmp.append([a,b])
tmp.sort()
l=0
r=sum(lis)*2
while l<=r:
    mid = l + (r-l)//2
    if check(mid):
        r = mid-1
    else:
        l = mid+1
if check(r):
    print(r)
elif check(l):
    print(l)
else:
    print(l+1)    





input=__import__('sys').stdin.readline
def check(x):
    last=[0]*(n+1)
    for i in tmp:
        if i[0]>x:
            break
        else:
            last[i[1]]=i[0]
    sal=[0]*(x+1)
    for i in range(1,n+1):
        sal[last[i]]+=lis[i-1]
    c=0
    for i in range(1,x+1):
        c+=1
        if sal[i]>=c:
            sal[i]-=c
            c=0
        else:
            c-=sal[i]
            sal[i]=0
    if sum(sal)*2<=c:
        return True
    else:
        return False        
n,m = list(map(int,input().split()))
lis = list(map(int,input().split()))
tmp=[]
for _ in range(m):
    a,b = list(map(int,input().split()))
    tmp.append([a,b])
tmp.sort()
l=0
r=sum(lis)*2
while l<=r:
    mid = l + (r-l)//2
    if check(mid):
        r = mid-1
    else:
        l = mid+1
if check(r):
    print(r)
elif check(l):
    print(l)
else:
    print(l+1)