using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace ConsoleApplication1
{
    public sealed class Treap<T>
    {
        private readonly Func<T, T, int> Comparer;
        private readonly Treap<T> Left;
        private readonly T Value;
        private readonly Treap<T> Right;

        // book keeping
        private readonly Random Rnd;
        private readonly int Height; // not needed, only used to ensure that our tree is mostly balanced
        private readonly int Priority;
        public readonly int Count;

        public Treap(Func<T, T, int> comparer)
        {
            this.Comparer = comparer;
            this.Priority = Int32.MinValue;
            this.Rnd = new Random();
        }

        private Treap(Func<T, T, int> comparer, Treap<T> left, T value, Treap<T> right, int priority)
        {
            this.Comparer = comparer;
            this.Left = left;
            this.Right = right;
            this.Value = value;

            this.Height = Math.Max(left.Height, right.Height) + 1;
            this.Count = left.Count + right.Count + 1;
            this.Rnd = left.Rnd;
            this.Priority = priority;
        }

        private Treap<T> Make(Treap<T> left, T value, Treap<T> right, int priority)
        {
            return new Treap<T>(Comparer, left, value, right, priority);
        }

        private Treap<T> Make(Treap<T> left, T value, Treap<T> right)
        {
            return Make(left, value, right, Rnd.Next(Int32.MinValue, Int32.MaxValue));
        }

        private bool IsEmpty { get { return Count == 0; } }

        public Treap<T> Insert(T v)
        {
            if (IsEmpty)
            {
                return Make(this, v, this);
            }
            else
            {
                int compare = Comparer(v, Value);
                if (compare < 0)
                {
                    return Make(Left.Insert(v), Value, Right, Priority).HeapifyLeft();
                }
                else if (compare > 0)
                {
                    return Make(Left, Value, Right.Insert(v), Priority).HeapifyRight();
                }
                else
                {
                    return this;
                }
            }
        }

        public Treap<T> HeapifyLeft()
        {
            if (this.Priority < Left.Priority)
            {
                return RotateRight();
            }
            return this;
        }

        public Treap<T> HeapifyRight()
        {
            if (this.Priority < Right.Priority)
            {
                return RotateLeft();
            }
            return this;
        }

        /// <summary>
        /// Left tree rotation.
        /// </summary>
        /// <remarks>
        ///       q      Right Rotation       p
        ///     /   \    --------------+    /   \
        ///    p     c                     a     q
        ///   / \        Left Rotation          / \
        ///  a   b       +-------------        b   c
        /// </remarks>
        private Treap<T> RotateLeft()
        {
            if (this.IsEmpty || this.Right.IsEmpty)
            {
                return this;
            }

            T p = this.Value;
            int pPriority = this.Priority;

            T q = this.Right.Value;
            int qPriority = this.Right.Priority;

            Treap<T> a = this.Left;
            Treap<T> b = this.Right.Left;
            Treap<T> c = this.Right.Right;
            return Make(Make(a, p, b, pPriority), q, c, qPriority);
        }

        /// <summary>
        /// Right tree rotation
        /// </summary>
        /// <remarks>
        ///       q      Right Rotation       p
        ///     /   \    --------------+    /   \
        ///    p     c                     a     q
        ///   / \        Left Rotation          / \
        ///  a   b       +-------------        b   c
        /// </remarks>
        private Treap<T> RotateRight()
        {
            if (this.IsEmpty || this.Left.IsEmpty)
            {
                return this;
            }

            T q = this.Value;
            int qPriority = this.Priority;

            T p = this.Left.Value;
            int pPriority = this.Left.Priority;

            Treap<T> a = this.Left.Left;
            Treap<T> b = this.Left.Right;
            Treap<T> c = this.Right;
            return Make(a, p, Make(b, q, c, qPriority), pPriority);
        }
    }
}