F - Rated Range
Source: atcoder
Difficulty: 525

Problem Statement
Takahashi plans to participate in
N
AtCoder contests.
In the
i
-th contest (
1 \leq i \leq N
), if his rating is between
L_i
and
R_i
(inclusive), his rating increases by
1
.
You are given
Q
queries in the following format:
An integer
X
is given. Assuming that Takahashi's initial rating is
X
, determine his rating after participating in all
N
contests.
Constraints
1 \leq N \leq 2 \times 10^5
1 \leq L_i \leq R_i \leq 5 \times 10^5
(1 \leq i \leq N)
1 \leq Q \leq 3 \times 10^5
For each query,
1 \leq X \leq 5 \times 10^5
.
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
L_1
R_1
L_2
R_2
\vdots
L_N
R_N
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Here,
\text{query}_i
is the
i
-th query in the form:
X
Output
Print
Q
lines. The
i
-th line should contain the answer to the
i
-th query.
Sample Input 1
5
1 5
1 3
3 6
2 4
4 7
3
3
2
5
Sample Output 1
6
6
8
For the 1st query, the rating changes as follows:
In the 1st contest, the rating is between
1
and
5
, so it increases by
1
, becoming
4
.
In the 2nd contest, the rating is not between
1
and
3
, so it remains
4
.
In the 3rd contest, the rating is between
3
and
6
, so it increases by
1
, becoming
5
.
In the 4th contest, the rating is not between
2
and
4
, so it remains
5
.
In the 5th contest, the rating is between
4
and
7
, so it increases by
1
, becoming
6
.
For the 2nd query, the rating increases in the 1st, 2nd, 3rd, and 5th contests, ending at
6
.
For the 3rd query, the rating increases in the 1st, 3rd, and 5th contests, ending at
8
.
Sample Input 2
10
1 1999
1 1999
1200 2399
1 1999
1 1999
1 1999
2000 500000
1 1999
1 1999
1600 2799
7
1
1995
2000
2399
500000
2799
1000
Sample Output 2
8
2002
2003
2402
500001
2800
1007
Sample Input 3
15
260522 414575
436426 479445
148772 190081
190629 433447
47202 203497
394325 407775
304784 463982
302156 468417
131932 235902
78537 395728
223857 330739
286918 329211
39679 238506
63340 186568
160016 361868
10
287940
296263
224593
101449
336991
390310
323355
177068
11431
8580
Sample Output 3
287946
296269
224599
101453
336997
390315
323363
177075
11431
8580

C++ solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+100 ;
int n , q , f[N] , tr[N] ;

int lowbit(int x){
    return x & -x ;
}

void add(int x , int k){
    if(x == 0)x = 1;
    while(x <= N){
        tr[x] += k ;
        x = x + lowbit(x) ;
    }
}

int query(int x){
    int ans = 0 ;
    while(x){
        ans += tr[x] ;
        x -= lowbit(x) ;
    }
    return ans ;
}

int find(int x){
    int l = 0 , r = N , ans = 0 ;
    while(l <= r){
        int mid = (l+r) >> 1 ;
        if(f[mid]+query(mid) >= x){    
            ans = mid ;
            r = mid-1 ;
        }else{
            l = mid+1 ;
        }
    }
    return ans ;
}

int main(){
    ios::sync_with_stdio(0) ;
    cin.tie(0);
    cin >> n ;
    for(int i = 1 ; i <= N ; i ++){
        f[i] = i ;
    }
    for(int i = 0 ; i < n ; i ++){
        int l , r ;
        cin >> l >> r ;
        int fl = find(l) , fr = find(r+1) ;
        add(fl , 1) ;
        add(fr , -1) ;
        // int x = f[2]+query(2) ;
        // cout << query(2) << ' ' ;
    }
    // cout << '\n' ;
    cin >> q ;
    while(q --){
        int x ; cin >> x ;
        // cout << f[x]+query(x) << ' ' << f[x] << ' ' << query(x) << '\n'  ;
        cout << f[x]+query(x) << '\n'  ;

    }
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
	"strconv"
)

var iost *Iost

type Iost struct {
	Scanner *bufio.Scanner
	Writer  *bufio.Writer
}

func NewIost(fp io.Reader, wfp io.Writer) *Iost {
	const BufSize = 2000005
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, BufSize), BufSize)
	return &Iost{Scanner: scanner, Writer: bufio.NewWriter(wfp)}
}
func (i *Iost) Text() string {
	if !i.Scanner.Scan() {
		panic("scan failed")
	}
	return i.Scanner.Text()
}
func (i *Iost) Atoi(s string) int                 { x, _ := strconv.Atoi(s); return x }
func (i *Iost) GetNextInt() int                   { return i.Atoi(i.Text()) }
func (i *Iost) Atoi64(s string) int64             { x, _ := strconv.ParseInt(s, 10, 64); return x }
func (i *Iost) GetNextInt64() int64               { return i.Atoi64(i.Text()) }
func (i *Iost) Atof64(s string) float64           { x, _ := strconv.ParseFloat(s, 64); return x }
func (i *Iost) GetNextFloat64() float64           { return i.Atof64(i.Text()) }
func (i *Iost) Print(x ...interface{})            { fmt.Fprint(i.Writer, x...) }
func (i *Iost) Printf(s string, x ...interface{}) { fmt.Fprintf(i.Writer, s, x...) }
func (i *Iost) Println(x ...interface{})          { fmt.Fprintln(i.Writer, x...) }
func isLocal() bool                               { return os.Getenv("NICKEL") == "BACK" }
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	if isLocal() {
		fp, _ = os.Open(os.Getenv("WELL_EVERYBODY_LIES_TOO_MUCH"))
	}
	iost = NewIost(fp, wfp)
	defer func() {
		iost.Writer.Flush()
	}()
	solve()
}
func solve() {
	n := iost.GetNextInt()
	const Max = 500001
	f := NewFenwickTree[int](Max + 1)
	search := func(x int) int {
		return sort.Search(Max+1, func(y int) bool {
			return y+f.Sum(0, y+1) >= x
		})

	}
	for i := 0; i < n; i++ {
		l := iost.GetNextInt() - 1
		r := iost.GetNextInt()
		sl := search(l)
		sr := search(r)
		f.Add(sl, 1)
		f.Add(sr, -1)
	}
	ans := make([]int, Max+1)
	for i := 0; i < Max+1; i++ {
		ans[i] = i + f.Sum(0, i+1)
	}
	q := iost.GetNextInt()
	for i := 0; i < q; i++ {
		x := iost.GetNextInt() - 1
		iost.Println(ans[x] + 1)
	}
}

type FenwickTree[T ~int | ~int64 | ~float64] []T

func NewFenwickTree[T ~int | ~int64 | ~float64](n int) FenwickTree[T] {
	return make(FenwickTree[T], n)
}

func (f FenwickTree[T]) Add(p int, x T) {
	for p++; p <= len(f); p += p & -p {
		f[p-1] += x
	}
}
func (f FenwickTree[T]) Sum(l, r int) T {
	return f.sum(r) - f.sum(l)
}
func (f FenwickTree[T]) sum(r int) T {
	var s T
	for ; r > 0; r -= r & -r {
		s += f[r-1]
	}
	return s
}

Java solution:
import java.io.*;
import java.lang.reflect.Array;
import java.nio.charset.StandardCharsets;
import java.util.*;
import java.util.function.IntFunction;
import java.util.function.IntToLongFunction;
import java.util.function.IntUnaryOperator;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public final class Main {
    public static void main(String[] args) throws IOException {
        run(System.in, new PrintStream(new BufferedOutputStream(System.out), false, StandardCharsets.UTF_8));
    }

    @SuppressWarnings({"DuplicatedCode", "SameParameterValue"})
    static void run(InputStream in, PrintStream out) throws IOException {
        FastScanner scanner = new FastScanner(in);

        var fenwickTree = new FenwickTree(new int[500_002]);
        var n = scanner.nextUint();
        for (int i = 0; i < n; i++) {
            var left = scanner.nextUint();
            var right = scanner.nextUint();

            var l = Math.max(1, left - i);
            var r = left;
            var effectiveLeft = -1;
            do {
                var m = l + (r - l) / 2;
                var rating = fenwickTree.prefixAccumulate(m + 1) + m;
                if (rating >= left) {
                    effectiveLeft = m;
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            } while (l <= r);

            if (effectiveLeft >= 1 && effectiveLeft <= right) {
                l = effectiveLeft;
                r = right;
                var effectiveRight = -1;
                do {
                    var m = l + (r - l) / 2;
                    var rating = fenwickTree.prefixAccumulate(m + 1) + m;
                    if (rating <= right) {
                        effectiveRight = m;
                        l = m + 1;
                    } else {
                        r = m - 1;
                    }
                } while (l <= r);

                if (effectiveLeft <= effectiveRight) {
                    fenwickTree.applyAt(effectiveLeft, 1);
                    fenwickTree.applyAt(effectiveRight + 1, -1);
                }
            }
        }

        var q = scanner.nextUint();
        for (int i = 0; i < q; i++) {
            var x = scanner.nextUint();
            out.println(x + fenwickTree.prefixAccumulate(x + 1));
        }

        out.flush();
    }

    @SuppressWarnings("DuplicatedCode")
    static class FenwickTree extends AbstractList<Integer> {
        private final int[] tree;

        public FenwickTree(int[] initialValues) {
            this(initialValues.length);

            for (int i = 0; i < initialValues.length; i++) {
                tree[i] = combineElements(tree[i], initialValues[i]);
                var j = toUpperBound(i);
                if (j < this.tree.length) {
                    tree[j] = combineElements(tree[j], tree[i]);
                }
            }
        }

        public FenwickTree(int size) {
            this.tree = neutralElements(size);
        }

        @Override
        public final Integer get(int index) {
            return plainGet(index);
        }

        public final int plainGet(int index) {
            return rangeAccumulate(index, index + 1);
        }

        @Override
        public final int size() {
            return tree.length;
        }

        @Override
        public final Integer set(int index, Integer element) {
            return set(index, element.intValue());
        }

        public final int rangeAccumulate(int from, int toExclusive) {
            if (from > toExclusive || from < 0 || toExclusive > tree.length) {
                throw new IllegalArgumentException("from=" + from + ", toExclusive=" + toExclusive + ", size=" + size());
            }

            if (from == toExclusive) {
                return neutralElement();
            } else if (from == 0) {
                return prefixAccumulate(toExclusive);
            } else {
                return combineElementsWithInverse(prefixAccumulate(toExclusive), prefixAccumulate(from));
            }
        }

        public final int prefixAccumulate(int toExclusive) {
            var i = toExclusive - 1;
            var res = neutralElement();
            while (i >= 0) {
                res = combineElements(res, tree[i]);
                i = toLowerBound(i) - 1;
            }

            return res;
        }

        public final int set(int index, int element) {
            var current = plainGet(index);
            var delta = combineElementsWithInverse(element, current);
            applyAt(index, delta);
            return current;
        }

        public final void applyAt(int index, int delta) {
            checkIndex(index);

            do {
                tree[index] = combineElements(tree[index], delta);
                index = toUpperBound(index);
            } while (index < size());
        }

        private static int toLowerBound(int i) {
            return i & (i + 1);
        }

        private static int toUpperBound(int i) {
            return i | (i + 1);
        }

        protected int neutralElement() {
            return 0;
        }

        protected int combineElements(int a, int b) {
            return a + b;
        }

        protected int combineElementsWithInverse(int a, int b) {
            return a - b;
        }

        private void checkIndex(int index) {
            if (index < 0 || index >= tree.length) {
                throw new IndexOutOfBoundsException("index=" + index + ", size=" + size());
            }
        }

        private int[] neutralElements(int n) {
            var elements = new int[n];
            if (n > 0 && elements[0] != neutralElement()) {
                Arrays.fill(elements, neutralElement());
            }

            return elements;
        }
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static void printIntsLn(PrintStream out, int... ints) {
        printIntsLn(out, ints, " ");
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static void printIntsLn(PrintStream out, int[] ints, String separator) {
        for (int i = 0; i < ints.length; i++) {
            if (i != 0) {
                out.print(separator);
            }

            out.print(ints[i]);
        }

        out.println();
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static void printLongsLn(PrintStream out, long... longs) {
        printLongsLn(out, longs, " ");
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static void printLongsLn(PrintStream out, long[] longs, String separator) {
        for (int i = 0; i < longs.length; i++) {
            if (i != 0) {
                out.print(separator);
            }

            out.print(longs[i]);
        }

        out.println();
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    @SafeVarargs
    static <T> void printObjectsLn(PrintStream out, T... objects) {
        printObjectsLn(out, List.of(objects), " ");
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static void printObjectsLn(PrintStream out, Collection<?> objects) {
        printObjectsLn(out, objects, " ");
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static void printObjectsLn(PrintStream out, Collection<?> objects, String separator) {
        var first = true;
        for (Object object : objects) {
            if (!first) {
                out.print(separator);
            }

            out.print(object);
            first = false;
        }

        out.println();
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static int minOf(int... is) {
        if (is.length == 0) {
            throw new IllegalArgumentException();
        }

        var res = Integer.MAX_VALUE;
        for (int i : is) {
            res = Math.min(res, i);
        }
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static int maxOf(int... is) {
        if (is.length == 0) {
            throw new IllegalArgumentException();
        }

        var res = Integer.MIN_VALUE;
        for (int i : is) {
            res = Math.max(res, i);
        }
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static long minOf(long... is) {
        if (is.length == 0) {
            throw new IllegalArgumentException();
        }

        var res = Long.MAX_VALUE;
        for (long i : is) {
            res = Math.min(res, i);
        }
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static long maxOf(long... is) {
        if (is.length == 0) {
            throw new IllegalArgumentException();
        }

        var res = Long.MIN_VALUE;
        for (long i : is) {
            res = Math.max(res, i);
        }
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static <T> ExtendedArrayList<T> fillList(int n, Supplier<T> supplier) {
        return fillList(n, ignore -> supplier.get());
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static <T> ExtendedArrayList<T> fillList(int n, IntFunction<T> valueAt) {
        var res = new ExtendedArrayList<T>(n);
        for (int i = 0; i < n; i++) {
            res.add(valueAt.apply(i));
        }

        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static <T> T[] fillArray(int n, Class<T> clazz, Supplier<T> supplier) {
        return fillArray(n, clazz, ignore -> supplier.get());
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static <T> T[] fillArray(int n, Class<T> clazz, IntFunction<T> valueAt) {
        @SuppressWarnings("unchecked") var res = (T[]) Array.newInstance(clazz, n);

        for (int i = 0; i < n; i++) {
            res[i] = valueAt.apply(i);
        }

        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused", "SameParameterValue"})
    static <T> T[] fillArray(int n, T value) {
        @SuppressWarnings("unchecked") var res = (T[]) Array.newInstance(value.getClass(), n);
        Arrays.fill(res, value);
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static int[] fillIntArray(int n, IntUnaryOperator valueAt) {
        var res = new int[n];
        for (int i = 0; i < n; i++) {
            res[i] = valueAt.applyAsInt(i);
        }
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static int[] fillIntArray(int n, int value) {
        var res = new int[n];
        Arrays.fill(res, value);
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static long[] fillLongArray(int n, IntToLongFunction valueAt) {
        var res = new long[n];
        for (int i = 0; i < n; i++) {
            res[i] = valueAt.applyAsLong(i);
        }
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static long[] fillLongArray(int n, long value) {
        var res = new long[n];
        Arrays.fill(res, value);
        return res;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    record BinaryString(BitSet bits, int length) {
        public BinaryString {
            if (length < 0) throw new IndexOutOfBoundsException("" + length);
        }

        @Override
        public String toString() {
            return IntStream.range(0, length)
                    .mapToObj(i -> bits.get(i) ? "1" : "0")
                    .collect(Collectors.joining());
        }
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    record BinaryGrid(BitSet[] bits, int w) {
        BinaryGrid {
            if (w < 0) throw new IndexOutOfBoundsException("w=" + w);
        }

        int h() {
            return bits.length;
        }

        BitSet row(int i) {
            return bits[i];
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            BinaryGrid that = (BinaryGrid) o;

            if (w != that.w) return false;
            return Arrays.equals(bits, that.bits);
        }

        @Override
        public int hashCode() {
            int result = Arrays.hashCode(bits);
            result = 31 * result + w;
            return result;
        }

        @Override
        public String toString() {
            return Arrays.stream(bits, 0, h())
                    .map(row -> IntStream.range(0, w).mapToObj(j -> row.get(j) ? "1" : "0").collect(Collectors.joining()))
                    .collect(Collectors.joining("\n"));
        }
    }

    @SuppressWarnings({"DuplicatedCode", "unused", "UnusedReturnValue"})
    static class ExtendedArrayList<T> extends ArrayList<T> {
        public ExtendedArrayList(int initialCapacity) {
            super(initialCapacity);
        }

        public ExtendedArrayList() {

        }

        public ExtendedArrayList(Collection<? extends T> c) {
            super(c);
        }

        T getFromEnd(int offset) {
            return get(size() - offset - 1);
        }

        T getFst() {
            return get(0);
        }

        T getLst() {
            return getFromEnd(0);
        }

        T removeLst() {
            return remove(size() - 1);
        }
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static final class Adj {
        static ExtendedArrayList<ExtendedArrayList<Integer>> undirected(int n, int[][] edges) {
            return undirected(n, edges, 1);
        }

        static ExtendedArrayList<ExtendedArrayList<Integer>> directed(int n, int[][] edges) {
            return directed(n, edges, 1);
        }

        @SuppressWarnings("SameParameterValue")
        static ExtendedArrayList<ExtendedArrayList<Integer>> undirected(int n, int[][] edges, int offset) {
            var res = fillList(n, () -> new ExtendedArrayList<Integer>(1));

            for (int[] edge : edges) {
                res.get(edge[0] - offset).add(edge[1] - offset);
                res.get(edge[1] - offset).add(edge[0] - offset);
            }

            return res;
        }

        @SuppressWarnings("SameParameterValue")
        static ExtendedArrayList<ExtendedArrayList<Integer>> directed(int n, int[][] edges, int offset) {
            var res = fillList(n, () -> new ExtendedArrayList<Integer>(1));

            for (int[] edge : edges) {
                res.get(edge[0] - offset).add(edge[1] - offset);
            }

            return res;
        }
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static long gcd(long a, long b) {
        while (b != 0) {
            var bb = a % b;
            a = b;
            b = bb;
        }

        return a;
    }

    @SuppressWarnings({"DuplicatedCode", "unused"})
    static int gcd(int a, int b) {
        while (b != 0) {
            var bb = a % b;
            a = b;
            b = bb;
        }

        return a;
    }


    @SuppressWarnings({"DuplicatedCode", "unused"})
    static final class FastScanner {
        private final InputStream in;
        private final byte[] buf = new byte[4 * 1024];
        private int a = 0;
        private int b = 0;

        FastScanner(InputStream in) {
            this.in = in;
        }

        byte nextByte() throws IOException {
            if (a < b) {
                byte v = buf[a];
                a += 1;
                return v;
            } else {
                b = in.read(buf);

                if (b < 0) {
                    throw new EOFException();
                } else {
                    a = 0;
                    return nextByte();
                }
            }
        }

        boolean hasNext() throws IOException {
            if (a < b) return true;
            else if (b < 0) return false;
            else {
                b = in.read(buf);
                a = 0;
                return hasNext();
            }
        }

        char nextChar() throws IOException {
            return (char) nextByte();
        }

        char nextNonWhitespaceChar() throws IOException {
            while (true) {
                var c = nextChar();
                if (!Character.isWhitespace(c)) {
                    return c;
                }
            }
        }

        long nextLong() throws IOException {
            while (true) {
                char c = nextChar();

                if (c == '-') {
                    c = nextChar();
                    if (isAsciiDigit(c)) {
                        return Math.negateExact(nextUlongImpl(c));
                    }
                } else if (isAsciiDigit(c)) {
                    return nextUlongImpl(c);
                }
            }
        }

        long[] nextLongs(int n) throws IOException {
            long[] res = new long[n];

            for (int i = 0; i < n; ++i) {
                res[i] = nextLong();
            }

            return res;
        }

        long[][] nextLongs(int rows, int cols) throws IOException {
            long[][] res = new long[rows][cols];

            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    res[i][j] = nextLong();
                }
            }

            return res;
        }

        long nextUlong() throws IOException {
            long res = nextLong();
            if (res < 0) throw new IllegalArgumentException("Expected a positive number, but got " + res);
            return res;
        }

        long[] nextUlongs(int n) throws IOException {
            long[] res = new long[n];

            for (int i = 0; i < n; ++i) {
                res[i] = nextUlong();
            }

            return res;
        }

        long[][] nextUlongs(int rows, int cols) throws IOException {
            long[][] res = new long[rows][cols];

            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    res[i][j] = nextUlong();
                }
            }

            return res;
        }

        int nextInt() throws IOException {
            return Math.toIntExact(nextLong());
        }

        int[] nextInts(int n) throws IOException {
            int[] res = new int[n];

            for (int i = 0; i < n; ++i) {
                res[i] = nextInt();
            }

            return res;
        }

        int[][] nextInts(int rows, int cols) throws IOException {
            int[][] res = new int[rows][cols];

            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    res[i][j] = nextInt();
                }
            }

            return res;
        }

        int nextUint() throws IOException {
            return Math.toIntExact(nextUlong());
        }

        int[] nextUints(int n) throws IOException {
            int[] res = new int[n];

            for (int i = 0; i < n; ++i) {
                res[i] = nextUint();
            }

            return res;
        }

        int[][] nextUints(int rows, int cols) throws IOException {
            int[][] res = new int[rows][cols];

            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < cols; ++j) {
                    res[i][j] = nextUint();
                }
            }

            return res;
        }

        <T> T[] nextObjects(int n, Class<T> clazz, IOExceptionThrowingSupplier<T> supplier) throws IOException {
            @SuppressWarnings("unchecked") T[] ret = (T[]) Array.newInstance(clazz, n);
            for (int i = 0; i < n; i++) {
                ret[i] = supplier.get();
            }

            return ret;
        }

        String nextLine() throws IOException {
            StringBuilder sb = new StringBuilder();
            char c = nextChar();

            while (c != '\n') {
                sb.append(c);

                if (!hasNext()) {
                    break;
                } else {
                    c = nextChar();
                }
            }

            if (!sb.isEmpty() && c == '\n' && sb.charAt(sb.length() - 1) == '\r') {
                sb.setLength(sb.length() - 1);
            }

            return sb.toString();
        }

        String[] nextLines(int n) throws IOException {
            if (n < 0) {
                n = nextUint();
                skipToNextLine();
            }

            return nextObjects(n, String.class, this::nextLine);
        }

        String[] nextLines() throws IOException {
            return nextLines(-1);
        }

        void skipToNextLine() throws IOException {
            //noinspection StatementWithEmptyBody
            while (nextChar() != '\n') {
                // just skip to next character
            }
        }

        BinaryString nextBinaryString() throws IOException {
            return nextBinaryString('1');
        }

        BinaryString nextBinaryString(char cTrue) throws IOException {
            return nextBinaryStringImpl(cTrue, -1);
        }

        BinaryString nextBinaryString(char cTrue, int length) throws IOException {
            if (length < 0) throw new IndexOutOfBoundsException("" + length);
            return nextBinaryStringImpl(cTrue, length);
        }

        BinaryGrid nextBinaryGrid(char cTrue) throws IOException {
            return nextBinaryGridImpl(cTrue, -1, -1);
        }

        BinaryGrid nextBinaryGrid(char cTrue, int h, int w) throws IOException {
            return nextBinaryGridImpl(cTrue, h, w);
        }

        private BinaryGrid nextBinaryGridImpl(char cTrue, int h, int w) throws IOException {
            if (h < 0) {
                h = nextUint();
                w = nextUint();

                if (h > 0) {
                    skipToNextLine();
                }
            }

            var bits = new BitSet[h];
            for (int i = 0; i < h; i++) {
                var row = new BitSet(w);

                for (int j = 0; j < w; j++) {
                    if (nextChar() == cTrue) {
                        row.set(j);
                    }
                }

                bits[i] = row;

                if (i != h - 1 || hasNext()) {
                    skipToNextLine();
                }
            }

            return new BinaryGrid(bits, w);
        }

        private BinaryString nextBinaryStringImpl(char cTrue, int length) throws IOException {
            if (length < 0) {
                length = nextUint();
                skipToNextLine();
            }

            BitSet bits = new BitSet(length);
            for (int i = 0; i < length; ++i) {
                if (nextChar() == cTrue) {
                    bits.set(i);
                }
            }

            return new BinaryString(bits, length);
        }

        private long nextUlongImpl(char firstDigit) throws IOException {
            long res = 0;
            char c = firstDigit;

            do {
                long res2 = 10 * res + (c - '0');
                if (res2 >= res) {
                    res = res2;
                } else {
                    throw new ArithmeticException("Long overflow");
                }

                if (hasNext()) {
                    c = nextChar();
                } else {
                    c = 0;
                }
            } while (isAsciiDigit(c));

            if (c != 0 && !isAsciiDigit(c)) {
                a -= 1;
            }

            return res;
        }

        private static boolean isAsciiDigit(char c) {
            return '0' <= c && c <= '9';
        }
    }

    interface IOExceptionThrowingSupplier<T> {
        T get() throws IOException;
    }
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

class BIT{//1-indexed
  constructor(n){
    this.a = Array(n+1).fill(0);
  }
  add(val,id){
    for(var i=id,a=this.a;i<a.length;i+=i&-i)a[i]+=val;
  }
  get(id){
    for(var r=0,i=id;i;i-=i&-i)r+=this.a[i];
    return r;
  }
  range(l,r){//[l,r]
    return this.get(r) - this.get(l-1);
  }
}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve());
}

function solve(){
  var n = next();
  var m = 5e5+1;
  var bi = new BIT(m+1);
  for(var i = 1; i <= m; i++){
    bi.add(1,i);
  }
  for(var i = 0; i < n; i++){
    var [l,r] = nexts(2);
    var li = f(l);
    var ri = f(r+1);
    bi.add(1,li);
    bi.add(-1,ri);
  }
  var q = next();
  while(q--){
    var x = next();
    print(bi.get(x));
  }

  function f(k){
    var l = 0, r = m;
    while(r-l>1){
      var mm = l+r>>1;
      var t = bi.get(mm);
      if(t < k)l = mm; else r = mm;
    }
    return r;
  }
}

Python solution:
'''
             🎌 (╯˘-˘)╯ 神様！仏様！直大様！(╯˘-˘)╯ 🎌              
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
                     Submitted by: kobejean                     
'''

def main():
    N, M = read(int), 500000
    L, R = read(ParallelRange[N])
    Q = read(int)
    X = read(list[int,Q])
    bit = BIT([1]*M)
    for l, r in zip(L,R):
        li, ri = bit.bisect_right(l), bit.bisect_right(r)
        bit.add(li, 1), bit.add(ri, -1)
    bit = bit.prelist()
    ans = [bit[x] for x in X]
    write(*ans)

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''

import os
import sys
import typing
from collections import deque
from io import BytesIO, IOBase
from numbers import Number
from types import GenericAlias
from typing import Callable, Collection, Iterator, Union


class FastIO(IOBase):
    BUFSIZE = 8192
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        BUFSIZE = self.BUFSIZE
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        BUFSIZE = self.BUFSIZE
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    stdin: 'IOWrapper' = None
    stdout: 'IOWrapper' = None
    
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable

    def write(self, s):
        return self.buffer.write(s.encode("ascii"))
    
    def read(self):
        return self.buffer.read().decode("ascii")
    
    def readline(self):
        return self.buffer.readline().decode("ascii")

sys.stdin = IOWrapper.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper.stdout = IOWrapper(sys.stdout)
from typing import TypeVar

_T = TypeVar('T')

class TokenStream(Iterator):
    stream = IOWrapper.stdin

    def __init__(self):
        self.queue = deque()

    def __next__(self):
        if not self.queue: self.queue.extend(self._line())
        return self.queue.popleft()
    
    def wait(self):
        if not self.queue: self.queue.extend(self._line())
        while self.queue: yield
 
    def _line(self):
        return TokenStream.stream.readline().split()

    def line(self):
        if self.queue:
            A = list(self.queue)
            self.queue.clear()
            return A
        return self._line()
TokenStream.default = TokenStream()

class CharStream(TokenStream):
    def _line(self):
        return TokenStream.stream.readline().rstrip()
CharStream.default = CharStream()


ParseFn = Callable[[TokenStream],_T]
class Parser:
    def __init__(self, spec: Union[type[_T],_T]):
        self.parse = Parser.compile(spec)

    def __call__(self, ts: TokenStream) -> _T:
        return self.parse(ts)
    
    @staticmethod
    def compile_type(cls: type[_T], args = ()) -> _T:
        if issubclass(cls, Parsable):
            return cls.compile(*args)
        elif issubclass(cls, (Number, str)):
            def parse(ts: TokenStream): return cls(next(ts))              
            return parse
        elif issubclass(cls, tuple):
            return Parser.compile_tuple(cls, args)
        elif issubclass(cls, Collection):
            return Parser.compile_collection(cls, args)
        elif callable(cls):
            def parse(ts: TokenStream):
                return cls(next(ts))              
            return parse
        else:
            raise NotImplementedError()
    
    @staticmethod
    def compile(spec: Union[type[_T],_T]=int) -> ParseFn[_T]:
        if isinstance(spec, (type, GenericAlias)):
            cls = typing.get_origin(spec) or spec
            args = typing.get_args(spec) or tuple()
            return Parser.compile_type(cls, args)
        elif isinstance(offset := spec, Number): 
            cls = type(spec)  
            def parse(ts: TokenStream): return cls(next(ts)) + offset
            return parse
        elif isinstance(args := spec, tuple):      
            return Parser.compile_tuple(type(spec), args)
        elif isinstance(args := spec, Collection):  
            return Parser.compile_collection(type(spec), args)
        elif isinstance(fn := spec, Callable): 
            def parse(ts: TokenStream): return fn(next(ts))
            return parse
        else:
            raise NotImplementedError()

    @staticmethod
    def compile_line(cls: _T, spec=int) -> ParseFn[_T]:
        if spec is int:
            fn = Parser.compile(spec)
            def parse(ts: TokenStream): return cls([int(token) for token in ts.line()])
            return parse
        else:
            fn = Parser.compile(spec)
            def parse(ts: TokenStream): return cls([fn(ts) for _ in ts.wait()])
            return parse

    @staticmethod
    def compile_repeat(cls: _T, spec, N) -> ParseFn[_T]:
        fn = Parser.compile(spec)
        def parse(ts: TokenStream): return cls([fn(ts) for _ in range(N)])
        return parse

    @staticmethod
    def compile_children(cls: _T, specs) -> ParseFn[_T]:
        fns = tuple((Parser.compile(spec) for spec in specs))
        def parse(ts: TokenStream): return cls([fn(ts) for fn in fns])  
        return parse
            
    @staticmethod
    def compile_tuple(cls: type[_T], specs) -> ParseFn[_T]:
        if isinstance(specs, (tuple,list)) and len(specs) == 2 and specs[1] is ...:
            return Parser.compile_line(cls, specs[0])
        else:
            return Parser.compile_children(cls, specs)

    @staticmethod
    def compile_collection(cls, specs):
        if not specs or len(specs) == 1 or isinstance(specs, set):
            return Parser.compile_line(cls, *specs)
        elif (isinstance(specs, (tuple,list)) and len(specs) == 2 and isinstance(specs[1], int)):
            return Parser.compile_repeat(cls, specs[0], specs[1])
        else:
            raise NotImplementedError()

class Parsable:
    @classmethod
    def compile(cls):
        def parser(ts: TokenStream): return cls(next(ts))
        return parser

class ParallelRange(tuple, Parsable):
    def __new__(cls, N):
        return super().__new__(cls, ([0]*N, [0]*N))

    @classmethod
    def compile(cls, N: int):
        def parse(ts: TokenStream):
            L, R = P = cls(N)
            for i in range(N):
                l, r = ts.line()
                L[i], R[i] = int(l)-1, int(r)
            return P
        return parse

from typing import Sequence


class BIT(Sequence[int]):
    def __init__(bit, v):
        if isinstance(v, int): bit.d, bit.n = [0]*v, v
        else: bit.build(v)
        bit.lb = 1<<(bit.n.bit_length()-1)

    def build(bit, data):
        bit.d, bit.n = data, len(data)
        for i in range(bit.n):
            if (r := i|i+1) < bit.n: bit.d[r] += bit.d[i]

    def add(bit, i, x):
        while i < bit.n:
            bit.d[i] += x
            i |= i+1

    def sum(bit, n: int) -> int:
        assert 0 <= n <= bit.n
        s = 0
        while n: s, n = s+bit.d[n-1], n&n-1
        return s

    def range_sum(bit, l, r):
        s = 0
        while r: s, r = s+bit.d[r-1], r&r-1
        while l: s, l = s-bit.d[l-1], l&l-1
        return s

    def __len__(bit) -> int:
        return bit.n
    
    def __getitem__(bit, i: int) -> int:
        s, l = bit.d[i], i&(i+1)
        while l != i: s, i = s-bit.d[i-1], i-(i&-i)
        return s
    get = __getitem__
    
    def __setitem__(bit, i: int, x: int) -> None:
        bit.add(i, x-bit[i])
    set = __setitem__

    def prelist(bit) -> list[int]:
        pre = [0]+bit.d
        for i in range(bit.n+1): pre[i] += pre[i&i-1]
        return pre

    def bisect_left(bit, v) -> int:
        return bit.bisect_right(v-1) if v>0 else 0
    
    def bisect_right(bit, v) -> int:
        i, ni = s, m = 0, bit.lb
        while m:
            if ni <= bit.n and (ns:=s+bit.d[ni-1]) <= v: s, i = ns, ni
            ni = (m:=m>>1)|i
        return i

from typing import Iterable, Type, Union, overload


@overload
def read() -> Iterable[int]: ...
@overload
def read(spec: int) -> list[int]: ...
@overload
def read(spec: Union[Type[_T],_T], char=False) -> _T: ...
def read(spec: Union[Type[_T],_T] = None, char=False):
    if not char and spec is None: return map(int, TokenStream.default.line())
    parser: _T = Parser.compile(spec)
    return parser(CharStream.default if char else TokenStream.default)

def write(*args, **kwargs):
    """Prints the values to a stream, or to stdout_fast by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", IOWrapper.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


def debug(*args, **kwargs):
    if debug.on:
        print(*args, **kwargs)
debug.on = False
# debug.on = True

if __name__ == "__main__":
    main()

Ruby solution:
class BIT
  attr_accessor(:arr, :size)
  def initialize(n)
    @size = n
    @arr = Array.new(@size+1,0)
  end

  def add(i,x)
    i += 1
    while i <= @size
      @arr[i] += x
      i += i & -i
    end
  end

  def sum(i)
    i += 1
    sum = 0
    while i > 0
      sum += @arr[i]
      i &= i - 1
    end
    sum
  end

  def lower_bound(x) #「bitがx個立っているところ」を指す！bsearchの代わりに
    return -1 if x <= 0
    ret = -1
    k = 1
    k <<= 1 while 2*k <= @size
    while k > 0
        if ret+k < @size && @arr[ret+k+1] < x
            x -= @arr[ret+k+1]
            ret += k
        end
        k >>= 1
    end
    ret + 1
  end

end

n = gets.to_i
max = 5*10**5+1
bit = BIT.new(max)
max.times do |i|
  next if i == 0
  bit.add(i,1)
end

n.times do
  l,r = gets.split.map(&:to_i)
  left = bit.lower_bound(l)
  right = bit.lower_bound(r+1) - 1
  bit.add(left,1)
  bit.add(right+1,-1)
end

q = gets.to_i
ans = []
q.times do
  x = gets.to_i
  ans << bit.sum(x)
end
puts ans