Help Regarding TLE in KQUERY

Problem Link : https://www.spoj.com/problems/KQUERY/5
I’m getting TLE in the following java code but similar C++ code is giving AC :

import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws IOException {
        InputReader sc = new InputReader(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
        SegmentTree tree = new SegmentTree(arr, n);
        int q = sc.nextInt();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() - 1;
            int r = sc.nextInt() - 1;
            int k = sc.nextInt();
            bw.write(tree.query(0, 0, n - 1, l, r, k) + "\n");
        }
        bw.flush();
    }
}

class SegmentTree {
    int[][] tree;
    int[] sizes;

    SegmentTree(int[] arr, int n) {
        tree = new int[4 * n][];
        sizes = new int[4 * n];
        build(0, arr, 0, n - 1);
    }

    void build(int pos, int[] arr, int l, int r) {
        if (l == r) {
            tree[pos] = new int[]{arr[l]};
            sizes[pos] = 1;
        } else {
            int mid = (l + r) / 2;
            build(pos * 2 + 1, arr, l, mid);
            build(pos * 2 + 2, arr, mid + 1, r);
            merge(pos, pos * 2 + 1, pos * 2 + 2);
        }
    }

    void merge(int pos, int leftChild, int rightChild) {
        int leftSize = sizes[leftChild];
        int rightSize = sizes[rightChild];
        tree[pos] = new int[leftSize + rightSize];
        int i = 0, j = 0, k = 0;

        while (i < leftSize && j < rightSize) {
            if (tree[leftChild][i] < tree[rightChild][j]) {
                tree[pos][k++] = tree[leftChild][i++];
            } else {
                tree[pos][k++] = tree[rightChild][j++];
            }
        }

        while (i < leftSize) tree[pos][k++] = tree[leftChild][i++];
        while (j < rightSize) tree[pos][k++] = tree[rightChild][j++];
        sizes[pos] = leftSize + rightSize;
    }

    int query(int pos, int tl, int tr, int l, int r, int k) {
        if (l > r) return 0;
        if (l == tl && tr == r) return search(tree[pos], k);
        int tm = (tl + tr) / 2;
        return query(pos * 2 + 1, tl, tm, l, Math.min(r, tm), k)
             + query(pos * 2 + 2, tm + 1, tr, Math.max(l, tm + 1), r, k);
    }

    int search(int[] array, int k) {
        int l = 0, r = array.length - 1, ans = array.length;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (array[mid] > k) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return array.length - ans;
    }
}

class InputReader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }
}