I was doing a competitive programming question whereby you are given an array of numbers, and then a certain number of queries. For each query, you are given 2 integers, 'a' and 'b'. So you're supposed to output the GCD of the remaining elements in the array (excluding a, b , and all the elements in between).

For example, if the array is : 16, 8, 24, 15, 20 and there are 2 queries (2, 3) and (1, 3), then output 1 is: 1 and output 2 is: 5. Note that the indexing is 1 based.

Here is my code, in which I've implemented the basic idea with a function for finding the GCD of an array passed to it.

public static void main(String args[]) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());

    while (t-- > 0) {   //This is the number of test cases
        String[] s1 = br.readLine().split(" ");
        int n = Integer.parseInt(s1[0]);          //Number of elements in array
        int q = Integer.parseInt(s1[1]);          //Number of queries

        String[] s2 = br.readLine().split(" ");
        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(s2[i]);
        }

        for (int i = 0; i < q; i++) {            //for each query
            String[] s3 = br.readLine().split(" ");
            int a = Integer.parseInt(s3[0]) - 1;
            int b = Integer.parseInt(s3[1]) - 1;

            int[] copy = new int[n - b + a - 1];     //this is so that the original array doesn't get messed up

            int index = 0;
            for (int j = 0; j < n; j++) {       //filing the array without the elements of the query
                if (j < a || j > b) {
                    copy[index] = arr[j];
                    index++;
                }
            }

            int fin = gcd(copy);
            System.out.println(fin);

        }

    }

}

private static int gcd(int a, int b) {
    while (b > 0) {
        int temp = b;
        b = a % b; // % is remainder
        a = temp;
    }
    return a;
}

private static int gcd(int[] input) {        //simple GCD calculator using the fact that GCD(a,b,c) === GCD((a,b),c)
    int result = input[0];
    for (int i = 1; i < input.length; i++)
        result = gcd(result, input[i]);
    return result;
}

The problem is that I'm getting AC on some of the parts (6 out of 10), and a TLE on the rest. Can someone suggest a better method to solve this problem, as my approach seems too slow, and almost impossible to be optimized any further?