// -----------------------------------------------------------------------------
// Binary Heap PQ                                                             C#
// -----------------------------------------------------------------------------

class BinaryHeapPQ<T> where T : IComparable
{
    int n = 0;
    T[] que = null;

    public BinaryHeapPQ() : this(1) { }

    public BinaryHeapPQ(int capacity)
    {
        que = new T[capacity + 1];
        n = 0;
    }

    public BinaryHeapPQ(T[] a)
    {
        n = a.Length;
        que = new T[n + 1];
        for (int i = 0; i < n; i++) que[i + 1] = a[i];
        for (int i = n / 2; i >= 1; i--) Sink(i);
    }

    public int Count { get { return n; } }

    public T Min { get { return que[1]; } }

    public void Insert(T x)
    {
        if (n == que.Length - 1) Resize(que.Length * 2);
        que[++n] = x;
        Swim(n);
    }

    public T ExtractMin()
    {
        Swap(1, n);
        T min = que[n--];
        Sink(1);
        que[n + 1] = default(T);
        return min;
    }

    void Swim(int k)
    {
        while (k > 1 && que[k / 2].CompareTo(que[k]) > 0) {
            Swap(k, k / 2);
            k = k / 2;
        }
    }

    void Sink(int k)
    {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && que[j].CompareTo(que[j + 1]) > 0) j++;
            if (que[k].CompareTo(que[j]) <= 0) break;
            Swap(k, j);
            k = j;
        }
    }

    void Resize(int capacity)
    {
        T[] temp = new T[capacity + 1];
        for (int i = 1; i <= n; i++) temp[i] = que[i];
        que = temp;
    }

    void Swap(int i, int j)
    {
        T temp = que[i];
        que[i] = que[j];
        que[j] = temp;
    }
}

// -----------------------------------------------------------------------------

// -----------------------------------------------------------------------------
// Index Binary Heap PQ                                                       C#
// -----------------------------------------------------------------------------

class IndexBinaryHeapPQ<T> where T : IComparable
{
    int maxN = 0;
    int n = 0;
    int[] pq = null;
    int[] qp = null;
    T[] keys = null;

    public IndexBinaryHeapPQ(int maxN)
    {
        this.maxN = maxN;
        n = 0;
        keys = new T[maxN + 1];
        pq = new int[maxN + 1];
        qp = new int[maxN + 1];
        for (int i = 0; i <= maxN; i++) qp[i] = -1;
    }

    public int Count { get { return n; } }
    public bool Contains(int ix) { return qp[ix] != -1; }
    public T KeyOf(int ix) { return keys[ix]; }
    public int MinIndex { get { return pq[1]; } }
    public T MinKey { get { return keys[pq[1]]; } }

    public bool Insert(int ix, T key)
    {
        if (Contains(ix)) return false;
        n++;
        qp[ix] = n;
        pq[n] = ix;
        keys[ix] = key;
        Swim(n);
        return true;
    }

    public bool Change(int ix, T key)
    {
        if (!Contains(ix)) return false;
        keys[ix] = key;
        Swim(qp[ix]);
        Sink(qp[ix]);
        return true;
    }

    public bool Increase(int ix, T key)
    {
        if (!Contains(ix)) return false;
        if (keys[ix].CompareTo(key) >= 0) return false;
        keys[ix] = key;
        Sink(qp[ix]);
        return true;
    }

    public bool Decrease(int ix, T key)
    {
        if (!Contains(ix)) return false;
        if (keys[ix].CompareTo(key) <= 0) return false;
        keys[ix] = key;
        Swim(qp[ix]);
        return true;
    }

    public bool Remove(int ix)
    {
        if (!Contains(ix)) return false;
        int index = qp[ix];
        Swap(index, n--);
        Swim(index);
        Sink(index);
        keys[ix] = default(T);
        qp[ix] = -1;
        return true;
    }

    public int ExtractMin()
    {
        int min = pq[1];
        Swap(1, n--);
        Sink(1);
        qp[min] = -1;
        keys[min] = default(T);
        pq[n + 1] = -1;
        return min;
    }

    void Swim(int k)
    {
        while (k > 1 && keys[pq[k / 2]].CompareTo(keys[pq[k]]) > 0) {
            Swap(k, k / 2);
            k = k / 2;
        }
    }

    void Sink(int k)
    {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && keys[pq[j]].CompareTo(keys[pq[j + 1]]) > 0) j++;
            if (keys[pq[k]].CompareTo(keys[pq[j]]) <= 0) break;
            Swap(k, j);
            k = j;
        }
    }

    void Swap(int i, int j)
    {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }
}

// -----------------------------------------------------------------------------