import static java.lang.Math.max;
import static java.lang.Math.min;

class KthLargestTwoArrays {
    /**
     * Given two sorted arrays of equal sizes, finds the median of the
     * array that comes out after `a` and `b` being merged. Runs in
     * linear time and does not require any extra space.
     *
     * The algorithm is similar to the arrays merging, but it
     * does not save the merged array, it just iterates through both
     * of them by n+1 items (thus stopping in the middle of an imaginary
     * merged array) and memorizes two consecutive elements. These
     * are the two elements laying exactly in the middle of merged array.
     *
     * (Since the length of the merged array is even, its median
     * is an average value of two elements in the middle.)
     *
     * @param a a sorted array
     * @param b a sorted array
     */
    static double medianTwoArraysLinear(double[] a, double[] b) {
        if (a.length != b.length) {
            throw new IllegalArgumentException(String.format(
                "Expected: len(a) == len(b)."
                + " Got: len(a) = %d, len(b) = %d",
                a.length, b.length
            ));
        }
        
        final int n = a.length;
        int i = 0, j = 0;
        // two consecutive elements of the merged array
        double mid1 = Double.NaN, mid2 = Double.NaN;
        for (int k = 0; k < n + 1; k++) {
            // here we also handle a special case when every element
            // of the first array is smaller than the smallest element
            // of the second array (and vice versa)
            if (j == n || i < n && a[i] < b[j]) {
                // put the previous value into the buffer
                mid1 = mid2;
                mid2 = a[i];
                i++;
            } else {
                mid1 = mid2;
                mid2 = b[j];
                j++;
            }
        }
        return (mid1 + mid2) / 2;
    }
    
    /**
     * A logarithmic-time algorithm that solves the same problem.
     * The basic idea is to compute the medians of both of the
     * arrays (well, these are not exactly "medians", in case the
     * array length is even, mid = A[n / 2], not the average value):
     *     A = [a1, a2, ..., mid1, ..., an] 
     *     B = [b1, b2, ..., mid2, ..., bn]
     * and after that there are three cases to consider:
     *
     *  - mid1 == mid2, which means (given len(A) == len(B)) that
     *    in every array there are n/2 elemets on the left side
     *    from the mid, so in the merged array mid1 and mid2 would
     *    be on n/2 + n/2 = n and n+1 positions (thus mid1 is the
     *    median of the merged array)
     *
     *  - mid1 &lt; mid2 means that the greatest element of the left
     *    side of the array A (A_left) is at most as large as the
     *    greatest element of B_left. And similarly the smallest
     *    element of B_right is at least as large as the smallest
     *    element of A_right.
     *
     *    This means that the left side of the imaginary merged array
     *    for sure would not end with an element from A_left, and
     *    the right side will not start with an value from B_right.
     *    (It can be easily seen from the example down below, just
     *    follow the steps of the merge algorithm.)
     *
     *    Thus the desired median elements are somewhere in
     *    A_right or B_left. When computing the median we can get rid
     *    of the same amount of elements on the right as on the left side
     *    and the result will not change in case the elements on the left
     *    are smaller than the median, meanwhile elements on the right
     *    are greater. So we can do here: A_left and B_right can be
     *    thrown away leaving us with just A_right and B_left -
     *    now we have the same problem but of half of the size.
     *
     *    Example:
     *    a = [ 1, 2, 3, 4, 8 ]
     *    b = [ 0, 3, 4, 5, 6 ]
     *    Merged: [ 0, 1*, 2*, 3, 3* | 4, 4*, 5, 6, 8* ]
     *    (elements from the first array are marked with asterisks)
     *
     *  - mid1 &gt; mid2 case is handled similarly.  */ 
    static double medianTwoArrays(double[] a, double[] b) {
        if (a.length != b.length) {
            throw new IllegalArgumentException(String.format(
                "Expected: len(a) == len(b)."
                + "Got: len(a) = %d, len(b) = %d",
                a.length, b.length
            ));
        } 
        final int n = a.length;
        int lo1 = 0, hi1 = n; // left subarray
        int lo2 = 0, hi2 = n; // right subarray

        while (hi1 - lo1 > 2) {
            double mid1 = a[lo1 + hi1 - 1 >>> 1];
            double mid2 = b[lo2 + hi2 - 1 >>> 1];

            if (mid1 > mid2) {
                // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
                double[] arraySwap = a; a = b; b = arraySwap;
                int swap = lo1; lo1 = lo2; lo2 = swap;
                swap = hi1; hi1 = hi2; hi2 = swap;
            } else if (a[lo1 + hi1 >>> 1] == b[lo2 + hi2 - 1 >>> 1]) {
                return a[lo1 + hi1 >>> 1];
            } else if (a[lo1 + hi1 - 1 >>> 1] == b[lo2 + hi2 >>> 1]) {
                return a[lo1 + hi1 >>> 1];
            }
            int cutLength = hi1 - lo1 - 1 >>> 1;
            lo1 += cutLength;
            hi2 -= cutLength;
        }

        if (hi1 - lo1 == 1) {
            return (a[lo1] + b[lo2]) / 2;
        } else {
            assert hi1 - lo1 == 2;
            // [a0, a1] [b0, b1] case
            // possible merged arrays:
            //   a0 < b0
            //   [a0, a1, b0, b1] mid = avg(a1, b0) -- a1 < b0 < b1
            //   [a0, b0, a1, b1] mid = avg(a1, b0) -- a1 < b1
            //   [a0, b0, b1, a1] mid = avg(b1, b0) -- a1 > b1
            //   
            //   a0 > b0
            //   [b0, a0, b1, a1] mid = avg(a0, b1) -- a1 > b1
            //   [b0, a0, a1, b1] mid = avg(a0, a1) -- a1 < b1
            //   [b0, b1, a0, a1] mid = avg(a0, b1) -- a1 > a0 > b1
            return (max(a[lo1], b[lo2])
                    + min(a[lo1 + 1], b[lo2 + 1])) / 2;
        }
    }

    /**
     * A linear solution of the same problem but now with
     * not necesserily equal-length sorted arrays.
     * @param a a sorted array
     * @param b a sorted array
     */
    static double medianTwoDifferentSizeArraysLinear(double[] a,
            double[] b) {
        assert isSorted(a) && isSorted(b);
        
        // if n := len(a) + len(b) is even, then the median of the
        // merged array equals to avg(mrgd[mid - 1], mrgd[mid])
        //
        // otherwise the median is just mrgd[mid]
        final int n = a.length + b.length;
        int mid = n >>> 1;
        double median1 = Double.NaN, median2 = Double.NaN;
        // a and b iterators respectively
        int i = 0, j = 0;

        for (int k = 0; k < mid + 1; k++) {
            median1 = median2;
            if (j == b.length || i < a.length && a[i] < b[j]) {
                median2 = a[i];
                i++;
            } else {
                median2 = b[j];
                j++;
            }
        }

        if (n % 2 == 0) {
            return (median1 + median2) / 2;
        } else {
            return median2;
        }
    }
    
    /**
     * Computes the median of two sorted not necessarily equal
     * length arrays. Runs in logarithmic time and does not
     * require any extra space.
     */
    static double medianTwoDifferentSizeArrays(double[] a, double[] b) {
        assert isSorted(a) && isSorted(b);

        int lo1 = 0, hi1 = a.length;
        int lo2 = 0, hi2 = b.length;

        while (hi1 - lo1 > 2 && hi2 - lo2 > 2) {
            double median1 = a[lo1 + hi1 - 1 >>> 1];
            double median2 = b[lo2 + hi2 - 1 >>> 1];

            if (median1 > median2) {
                // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
                double[] arraySwap = a; a = b; b = arraySwap;
                int swap = lo1; lo1 = lo2; lo2 = swap;
                swap = hi1; hi1 = hi2; hi2 = swap;
            } else if (a[lo1 + hi1 >>> 1] == b[lo2 + hi2 - 1 >>> 1]) {
                return a[lo1 + hi1 >>> 1];
            } else if (a[lo1 + hi1 - 1 >>> 1] == b[lo2 + hi2 >>> 1]) {
                return a[lo1 + hi1 - 1 >>> 1];
            }
            // -1 to cut [a0, a1, a2, a3] to [a1, a2, a3]
            // not to just [a2, a3]
            int cutLength = min((hi1 - lo1 - 1) >>> 1,
                    (hi2 - lo2 - 1) >>> 1);
            lo1 += cutLength;
            hi2 -= cutLength;
        }
        return medianBaseCase(a, lo1, hi1, b, lo2, hi2);
    }
    
    /**
     * A method designed to handle the base cases when calculating
     * the median of two sorted arrays.
     */
    private static double medianBaseCase(
            double[] a, int lo1, int hi1,
            double[] b, int lo2, int hi2) {
        assert hi1 - lo1 <= 2 || hi2 - lo2 <= 2;
        assert isSorted(a, lo1, hi1) && isSorted(b, lo2, hi2);
        assert rangeCheck(a, lo1, hi1) && rangeCheck(a, lo1, hi1);
        
        if (hi1 - lo1 > hi2 - lo2) {
            // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
            double[] arraySwap = a; a = b; b = arraySwap;
            int swap = hi1; hi1 = hi2; hi2 = swap;
            swap = lo1; lo1 = lo2; lo2 = swap;
        }
        
        int aLength = hi1 - lo1;
        int bLength = hi2 - lo2;

        if (aLength == 0 && bLength == 0) {
            return Double.NaN;
        }
        if (aLength == 2 && bLength == 2) {
            return twoTwoMedian(a, lo1, hi1, b, lo2, hi2);
        }
        if (aLength == 1 && bLength == 1) {
            return (a[lo1] + b[lo2]) / 2;
        }
        if (aLength == 1 && bLength == 2) {
            return oneTwoMedian(a, lo1, hi1, b, lo2, hi2);
        }
        
        int mid = (lo2 + hi2) >>> 1;
        if (aLength == 0) {
            if (bLength % 2 == 0) {
                return (b[mid - 1] + b[mid]) / 2;
            } else {
                return b[mid];
            }
        }
        if (aLength == 1) {
            // [1, 3, 5, 7] -> (insert 2, 4, 6)
            // [1, 2*, 3, 5, 7], [1, 3, 4*, 5, 7] or [1, 3, 5, 6*, 7]
            if (bLength % 2 == 0) {
                if (a[lo1] < b[mid - 1]) {
                    return b[mid - 1];
                } else if (b[mid - 1] < a[lo1] && a[lo1] < b[mid]) {
                    return a[lo1];
                } else {
                    return b[mid];
                }
            // [1, 3, 5] -> (insert 0, 2, 4, 6)
            // [0*, 1, 3, 5], [1, 2*, 3, 5],
            // [1, 3, 4*, 5], [1, 3, 5, 6*]
            } else {
                if (a[lo1] < b[mid - 1]) {
                    return (b[mid - 1] + b[mid]) / 2;
                } else if (b[mid - 1] < a[lo1] && a[lo1] < b[mid + 1]) {
                    return (b[mid] + a[lo1]) / 2;
                } else {
                    return (b[mid] + b[mid + 1]) / 2;
                }
            }
        }
        if (aLength == 2) {
            // [2, 5, 8, 11] -> (insert [0, 1], [3, 4], [6, 7]...)
            // [0*, 1*, 2, 5, 8, 11], [2, 3*, 4*, 5, 8, 11]
            // [2, 5, 6*, 7*, 8, 11], [2, 5, 8, 9*, 10*, 11]
            // [2, 5, 8, 11, 12*, 13*]
            if (bLength % 2 == 0) {
                if (a[lo1 + 1] < b[mid - 2]) {
                    return (b[mid - 2] + b[mid - 1]) / 2;
                } else if (b[mid + 1] < a[lo1]) {
                    return (b[mid] + b[mid + 1]) / 2;
                } else {
                    return twoTwoMedian(a, lo1, hi1, b, mid - 1, mid + 1);
                }
            // [2, 5, 8] -> (insert [0, 1], [3, 4], [6, 7], [9, 10])
            // [0*, 1*, 2, 5, 8], [2, 3*, 4*, 5, 8]
            // [2, 5, 6*, 7*, 8], [2, 5, 8, 9*, 10*]
            } else {
                if (a[lo1 + 1] < b[mid - 1]) {
                    return b[mid - 1];
                } else if (b[mid + 1] < a[lo1]) {
                    return b[mid + 1];
                } else {
                    return oneTwoMedian(b, mid, mid + 1, a, lo1, hi1);
                }
            }
        }
        return Double.NaN;
    }
    
    /**
     * Returns the k-th largest element among two sorted arrays
     * a and b. Runs in linear time.
     */
    static double kthLargestLinear(double[] a, double[] b, int k) {
        assert isSorted(a) && isSorted(b);

        if (k < 0 || k >= a.length + b.length) {
            throw new IndexOutOfBoundsException(String.format(
                "Got: len(a) = %d, len(b) = %d, k = %d",
                a.length, b.length, k
            ));
        }
        
        double last = Double.NaN;
        int indexA = 0, indexB = 0;
        for (int i = 0; i < k + 1; i++) {
            if (indexB == b.length
                    || indexA < a.length && a[indexA] < b[indexB]) {
                last = a[indexA];
                indexA++;
            } else {
                last = b[indexB];
                indexB++;
            }
        }
        return last;
    }
    
    /**
     * Finds the k-th largest element among two sorted arrays.
     * Runs in O(lgk) time.
     */
    static double kthLargest(double[] a, double[] b, int k) {
        assert isSorted(a) && isSorted(b);

        if (k < 0 || k >= a.length + b.length) {
            throw new IndexOutOfBoundsException(String.format(
                "Got: len(a) = %d, len(b) = %d, k = %d",
                a.length, b.length, k
            ));
        }

        int lo1 = 0, hi1 = a.length;
        int lo2 = 0, hi2 = b.length;

        while (k >= 0) {
            // in case one of the arrays is empty, return the k-th
            // element of the non-empty array
            if (lo1 == hi1) {
                return b[lo2 + k];
            }
            if (lo2 == hi2) {
                return a[lo1 + k];
            }
            // (at this point each array contains at least 1 element)
            if (k == 0) {
                return min(a[lo1], b[lo2]);
            }
            // keep the reference to the smaller array in the variable `a`
            // for simplicity
            if (hi1 - lo1 > hi2 - lo2) {
                // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
                double[] arraySwap = a; a = b; b = arraySwap;
                int swap = lo1; lo1 = lo2; lo2 = swap;
                swap = hi1; hi1 = hi2; hi2 = swap;
            }
            // if one of the arrays' length is <= k + 1 / 2, it might be
            // the case that all the elements from this array are
            // less than the k-th largest element of the two arrays
            if (hi1 - lo1 <= (k + 1) / 2) {
                if (a[hi1 - 1] < b[lo2 + k  - (hi1 - lo1)]) {
                    return b[lo2 + k  - (hi1 - lo1)];
                } else {
                    lo2 += (k + 1) / 2;
                    k -= (k + 1) / 2;
                }
            } else {
                if (a[lo1 + k / 2] == b[lo2 + k / 2]) {
                    return a[lo1 + k / 2];
                }
                if (a[lo1 + k / 2] > b[lo2 + k / 2]) {
                    // swap(a, b); swap(lo1, lo2); swap(hi1, hi2);
                    double[] arraySwap = a; a = b; b = arraySwap;
                    int swap = lo1; lo1 = lo2; lo2 = swap;
                    swap = hi1; hi1 = hi2; hi2 = swap;
                }
                lo1 += (k + 1) / 2;
                k -= (k + 1) / 2;
            }    
        }
        return Double.NaN;
    }

    private static double oneTwoMedian(
            double[] a, int lo1, int hi1,
            double[] b, int lo2, int hi2) {
        assert hi1 - lo1 == 1 && hi2 - lo2 == 2;
        // return a0 + b0 + b1 - min(a0, b0) - max(a0, b1);
        // return max(a0, b0) + min(0, b1 - a0);
        return max(a[lo1], b[lo2]) + min(0, b[lo2 + 1] - a[lo1]);
    }

    private static double twoTwoMedian(
            double[] a, int lo1, int hi1,
            double[] b, int lo2, int hi2) {
        assert hi1 - lo1 == 2 && hi2 - lo2 == 2;

        return (max(a[lo1], b[lo2]) + min(a[lo1 + 1], b[lo2 + 1])) / 2;
    }
    
    /**
     * Checks if the array of doubles is sorted.
     * Used solely for assertions tests.
     */
    private static boolean isSorted(double[] a, int lo, int hi) {
        assert rangeCheck(a, lo, hi)
            : String.format("len(a) = %d, lo = %d, hi = %d",
                a.length, lo, hi);

        for (int i = lo; i < hi - 1; i++) {
            if (a[i] > a[i + 1]) {
                return false;
            }
        }
        return true;
    }

    private static boolean isSorted(double[] a) {
        return isSorted(a, 0, a.length);
    }
    
    /**
     * Checks if the specified interval belongs to the array.
     * Returns false in case it does not, the interval is defined
     * incorrectly (empty intervals are acceptable) or a == null.
     *
     * Used solely for assertions tests.
     */
    private static boolean rangeCheck(double[] a, int lo, int hi) {
        if (a == null) {
            return false;
        } else if (lo < 0 || lo >= a.length && lo != 0
                || hi < 0 || hi > a.length) {
            return false;
        } else if (lo > hi) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        double[] a = { 0, 2, 4, 6, 8 };
        double[] b = { 1, 3, 5, 7, 9 };
        int k = 4;
        System.out.println(medianTwoArraysLinear(a, b));
        System.out.println(medianTwoArrays(a, b));
        
        System.out.println(medianTwoDifferentSizeArraysLinear(a, b));
        System.out.println(medianTwoDifferentSizeArrays(a, b));
        
        System.out.println(kthLargestLinear(a, b, k));
        System.out.println(kthLargest(a, b, k));
    }
}