ExampleTreap

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Example_treap
{
    class Program
    {
        static Random rand = new Random();
        public class Treap
        {
            private class Node
            {
                //public int x;
                //public int y;
                public object x;
                public object y;

                public Node Left;
                public Node Right;

                public Node(object x, object y, Node left = null, Node right = null)
                {
                    this.x = x;
                    this.y = y;
                    this.Left = left;
                    this.Right = right;
                }

                public Node()
                {
                    x = null;
                    y = null;
                    Left = null;
                    Right = null;
                }

                //public Treap (int a, int b)
                //{
                //    x = a;
                //    y = b;
                //    Left = null;
                //    Right = null;
                //}

                public static Node Merge(Node L, Node R)
                {
                    if (L == null) return R;
                    if (R == null) return L;

                    int cmp = ((IComparable)(L.y)).CompareTo(R.y);
                    //if (L.y > R.y)
                    if (cmp > 0)
                    {
                        var newR = Merge(L.Right, R);
                        return new Node(L.x, L.y, L.Left, newR);
                    }
                    else
                    {
                        var newL = Merge(L, R.Left);
                        return new Node(R.x, R.y, newL, R.Right);
                    }
                }

                public void Split(object x, out Node L, out Node R)
                {
                    Node newTree = null;
                    int cmp = ((IComparable)(this.x)).CompareTo(x);
                    //if (this.x <= x)
                    if(cmp <= 0)
                    {
                        if (Right == null)
                            R = null;
                        else
                            Right.Split(x, out newTree, out R);
                        L = new Node(this.x, y, Left, newTree);
                    }
                    else
                    {
                        if (Left == null)
                            L = null;
                        else
                            Left.Split(x, out L, out newTree);
                        R = new Node(this.x, y, newTree, Right);
                    }
                }

                public Node Add(object x)
                {
                    Node l, r;
                    Split(x, out l, out r);
                    Node m = new Node(x, rand.Next(200));
                    return Merge(Merge(l, m), r);
                }

                public  Node Remove(object x)
                {
                    Node l, m, r;
                    Split((int)x - 1, out l, out r);
                    r.Split(x, out m, out r);
                    return Merge(l, r);
                }

                public void Preorder(Node r)
                {
                    if (r != null)
                    {
                        Console.Write("{0} ", r.x);
                        Preorder(Left);
                        Preorder(Right);
                    }
                }
            }

            Node tree;
            public Treap()
            {
                tree = null;
            }

            public void Add (object x)
            {
                tree.Add(x);
            }

            public void Remove (object x)
            {
                tree.Remove(x);
            }

            public void Preorder()
            {
                tree.Preorder(tree);
            }

        }




                //public static Treap Build(int[] xs, int[] ys)
                //{
                //    Debug.Assert(xs.Length == ys.Length);

                //    var tree = new Treap(xs[0], ys[0]);
                //    var last = tree;

                //    for (int i = 1; i < xs.Length; ++i)
                //    {
                //        if (last.y > ys[i])
                //        {
                //            last.Right = new Treap(xs[i], ys[i], parent: last);
                //            last = last.Right;
                //        }
                //        else
                //        {
                //            Treap cur = last;
                //            while (cur.Parent != null && cur.y <= ys[i])
                //                cur = cur.Parent;
                //            if (cur.y <= ys[i])
                //                last = new Treap(xs[i], ys[i], cur);
                //            else
                //            {
                //                last = new Treap(xs[i], ys[i], cur.Right, null, cur);
                //                cur.Right = last;
                //            }
                //        }
                //    }

                //    while (last.Parent != null)
                //        last = last.Parent;
                //    return last;
                //}
        //public class BinaryTreap
        //{

        //    class Node
        //    {
        //        private static Random random = new Random();

        //        public object Priority;
        //        public object Key;


        //        public Node Left, Right;

        //        public Node(object key,
        //            Node left = null, Node right = null)
        //        {
        //            Priority = random.Next(); Key = key;
        //            Left = left; Right = right;
        //        }
        //        public Node()
        //        {
        //            Priority = null;
        //            Key = null;
        //            Left = null;
        //            Right = null;

        //        }
        //    }


        //    private Node root;

        //    private Node Set(Node root, Node child)
        //    {
        //        if (root == null) return child;

        //        int cmp = ((IComparable)child.Key).CompareTo(root.Key);
        //        if (cmp == 0)
        //            return child;
        //        else if (cmp > 0)
        //        {
        //            root.Right = Set(root.Right, child);
        //            int cmp1 = ((IComparable)root.Right.Priority).CompareTo(root.Priority);
        //            if (cmp1 < 0)
        //                root = LRotate(root);
        //        }
        //        else if (cmp < 0)
        //        {
        //            root.Left = Set(root.Left, child);
        //            int cmp2 = ((IComparable)root.Left.Priority).CompareTo(root.Priority);
        //            if (cmp2 < 0)
        //                root = RRotate(root);
        //        }
        //        return root;
        //    }

        //    private Node Delete(Node root, int key)
        //    {
        //        if (root == null) return null;

        //        int cmp = key.CompareTo(root.Key);
        //        if (cmp < 0) root.Left = Delete(root.Left, key);
        //        if (cmp > 0) root.Right = Delete(root.Right, key);
        //        if (cmp == 0)
        //        {
        //            if (root.Left != null && root.Right != null)
        //            {
        //                int cmp1 = ((IComparable)root.Left.Priority).CompareTo(root.Right.Priority);
        //                if (cmp1 < 0)
        //                    root = RRotate(root);
        //                else
        //                    root = LRotate(root);
        //            }
        //            else if (root.Left != null) root = RRotate(root);
        //            else if (root.Right != null) root = LRotate(root);
        //            else return null;
        //            root = Delete(root, key);
        //        }
        //        return root;
        //    }

        //    private Node LRotate(Node root)
        //    {
        //        Node temp = root.Right;
        //        root.Right = temp.Left;
        //        temp.Left = root;
        //        return temp;
        //    }
        //    private Node RRotate(Node root)
        //    {
        //        Node temp = root.Left;
        //        root.Left = temp.Right;
        //        temp.Right = root;
        //        return temp;
        //    }
    //private IEnumerable<Node> InOrder(Node root)
    //{
    //    if (root == null)
    //        yield break;

    //    foreach (Node child in InOrder(root.Left).Append(root).Concat(InOrder(root.Right)))
    //        yield return child;
    //}



        //    Treap treap;
        //    public Tree()
        //    {
        //        treap = null;
        //    }

        //    private Tree(Treap r)
        //    {
        //        treap = r;
        //    }
        //    public void Add(int a)
        //    {
        //        treap.Add(a);
        //    }
        //  public static void LevelPrint(Treap r)
        //        {
        //            Queue<Treap> queue = new Queue<Treap>();
        //            Console.WriteLine("{0} ", r.x);
        //            int temp = (int)r.x; ;
        //            queue.Enqueue(r);
        //            while (queue.Count != 0)
        //            {
        //                if (temp > (int)queue.Peek().x)
        //                    Console.WriteLine();
        //                temp = (int)queue.Peek().x;
        //                if (queue.Peek().Left != null)
        //                {
        //                    Console.Write("{0} ", queue.Peek().Left.x);
        //                    queue.Enqueue(queue.Peek().Left);

        //                }
        //                if (queue.Peek().Right != null)
        //                {
        //                    Console.Write("{0} ", queue.Peek().Right.x);
        //                    queue.Enqueue(queue.Peek().Right);
        //                }
        //                queue.Dequeue();
        //            }
        //        }
        //}

        static void Main(string[] args)
        {
            StreamReader fin = new StreamReader("input.txt");
            string temp = fin.ReadToEnd();
            string[] numbers = temp.Split(' ');
            fin.Close();
            //Treap treap = new Treap(4, 3);
            //foreach (string item in numbers)
            //    treap.Add(int.Parse(item));
            //treap.Preorder(treap);
            ////Treap.LevelPrint(treap);
     //var t = new BinaryTreap <int, int>();
            Treap  tr = new Treap();
            foreach (string item in numbers)
                tr.Add(int.Parse(item));
            tr.Preorder();
        }
    }
}