/** FenWick Minimum Tree for Range Minimum Queries by baobab */

/** http://stackoverflow.com/questions/31106459/how-to-adapt-fenwick-tree-to-answer-range-minimum-queries/34602284#34602284 */

class FenwickMin implements RMQ {
    long n;
    long[] original;
    long[] bottomUp;
    long[] topDown;

    public FenwickMin(int n) {
        this.n = n;
        original = new long[n+2];
        bottomUp = new long[n+2];
        topDown = new long[n+2];
    }

    @Override
    public void set(int modifiedNode, long value) {
        long replaced = original[modifiedNode];
        original[modifiedNode] = value;
        // Update left tree
        int i = modifiedNode;
        long v = value;
        while (i <= n) {
            if (v > bottomUp[i]) {
                if (replaced == bottomUp[i]) {
                    v = Math.min(v, original[i]);
                    for (int r=1 ;; r++) {
                        int x = (i&-i)>>>r;
                        if (x == 0) break;
                        int child = i-x;
                        v = Math.min(v, bottomUp[child]);
                    }
                } else break;
            }
            if (v == bottomUp[i]) break;
            bottomUp[i] = v;
            i += (i&-i);
        }
        // Update right tree
        i = modifiedNode;
        v = value;
        while (i > 0) {
            if (v > topDown[i]) {
                if (replaced == topDown[i]) {
                    v = Math.min(v, original[i]);
                    for (int r=1 ;; r++) {
                        int x = (i&-i)>>>r;
                        if (x == 0) break;
                        int child = i+x;
                        if (child > n+1) break;
                        v = Math.min(v, topDown[child]);
                    }
                } else break;
            }
            if (v == topDown[i]) break;
            topDown[i] = v;
            i -= (i&-i);
        }
    }

    @Override
    public long getMin(int a, int b) {
        long min = original[a];
        int prev = a;
        int curr = prev + (prev&-prev); // parent right hand side
        while (curr <= b) {
            min = Math.min(min, topDown[prev]); // value from the other tree
            prev = curr;
            curr = prev + (prev&-prev);;
        }
        min = Math.min(min, original[prev]);
        prev = b;
        curr = prev - (prev&-prev); // parent left hand side
        while (curr >= a) {
            min = Math.min(min,bottomUp[prev]); // value from the other tree
            prev = curr;
            curr = prev - (prev&-prev);
        }
        return min;
    }

}