In this problem, we are given a list of integers and a list of ranges. For each range, we want to count how many integers in the list are within the given range.

If we only had one range, we could just count the number of integers directly. However, with many ranges, naively counting the number of integers directly will be too slow.

A common thing to try when counting the number of integers between $A$ and $B$ that satisfy a condition is to count the number of integers from $0$ to $B$ that satisfy the condition, and subtract the count of integers from $0$ to $A-1$ that satisfy the condition.

If we try to follow that approach, we need a fast way to count the number of integers from $0$ to $B$ in the list. If we sort the list of integers, then we can binary search for the largest integer that is less than or equal to $B$. This lets us answer queries in $O(\log N)$ time, for a runtime of $O((N+Q) \log N)$.

Here is my Java code.

import java.io.*;
import java.util.*;
public class haybales {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("haybales.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("haybales.out")));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		int[] list = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			list[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.sort(list);
		for(int i = 0; i < q; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			pw.println(countLEQ(list, b) - countLEQ(list, a-1));
		}
		pw.close();
	}
	public static int countLEQ(int[] list, int limit) {
		if(list[0] > limit) {
			return 0;
		}
		int min = 0;
		int max = list.length-1;
		// list[min] is guaranteed to be <= limit
		while(min != max) {
			int mid = (min+max+1)/2;
			if(list[mid] <= limit) {
				min = mid;
			}
			else {
				max = mid-1;
			}
		}
		return min + 1;
	}
}