class Solution {
    public int[] kthSmallestPrimeFraction(int[] A, int k) {
        Arrays.sort(A);
        double gap=(A[0]+0.0)/A[A.length-1];
        double l=gap,r=1.0;
        for(int i=0;i<A.length/2;i++){
             int temp = A[i];
             A[i] = A[A.length - i - 1];
             A[A.length - i - 1] = temp;
        }
        
        int res[]=new int[2];
        
        while(r-l>=0.00000001){
            double mid=l+(r-l)/2;
            Queue<Integer>q=new LinkedList<>();
            int cnt=0;
            double max=-1;
            int arr[]=new int[2];
            for(int i=0;i<A.length;i++){
                double cur=A[i];
                while(q.size()>0&&(cur/q.peek())<=mid){
                    int peek=q.poll();
                    double curM=cur/peek;
                    if(curM>max){
                        max=curM;
                        arr[0]=A[i];
                        arr[1]=peek;
                    }
                }

                q.add(A[i]);
                cnt+=(i+1-q.size());
            }
            if(cnt>=k){
                res=arr;
                r=mid-0.0000001;
            }else{
                l=mid+0.0000001;
            }
           
        }
        return res;
    }
}
//5 3 2 1