I was trying to solve a competitive programming question in java.
Original question: You will be given intensities Ai of N bugs. Now relative intensity of a bug can be calculated by taking the GCD of intensities of the rest of N-1 bugs. Given Q queries containing a single integer X you have to find the number of bugs having relative intensity greater than X. where

 1 <= N <= 10^5
 1 <= Q <= 10^5
 1 <= Ai <= 10^9
 1 <= X <= 10^5

I am getting TLE for 6 TCs out of 10. Can anyone help me for feasible solution?

My Code:

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int t=sc.nextInt();
    int []arr=new int[n];
    for (int i = 0; i < n; i++) {
        arr[i]=sc.nextInt();
    }
    arr=mergeSort(arr);
    int gcd=arr[0];
    for(int i = 1; i < n; i++){
         gcd = gcd(gcd, arr[i]);
    }
    while(t-->0){
        int comp=sc.nextInt();
        int count=0;
        if (arr[1]>gcd) {
            int tempgcd=arr[1];
            for(int i = 2; i < n; i++){
                 tempgcd = gcd(tempgcd, arr[i]);
            }
            if (tempgcd>comp) {
                ++count;
            }
        }
        if (gcd>comp) {
            count=count+n-1;
        }
        System.out.println(count);
    }
    sc.close();

}