Python3 implementation of the approach
from bisect import bisect as upper_bound NEW_LINE from bisect import bisect_left as lower_bound NEW_LINE from math import floor NEW_LINE N = 1000005 NEW_LINE MAX = 10 ** 18 NEW_LINE