using System;

public class Program

{

    public static Queue<int> CloneQueue(Queue<int> myQu) // O(n): n is the number of elements in the list

    {

        Queue<int> tmp = new Queue<int>(); // בניית תור עזר

        Queue<int> retQu = new Queue<int>(); // בניית תור להחזיר למשתמש

        while (!myQu.IsEmpty()) // מעבר על כל התור

        {

            int removed = myQu.Remove(); // כדי לאחסן את האיבר ב-2 התורים נאחסן את ערכו במשנה שאותו נציב בכל תור

            tmp.Insert(removed);

            retQu.Insert(removed);

        }

        while (!tmp.IsEmpty()) // החזרת התור למצבו המקורי

        {

            myQu.Insert(tmp.Remove());

        }

        return retQu;

    }

​

    public static Queue<int> RemoveElementsFromQueue(Queue<int> qu, int num) // O(n): n is the number of elements in the list

    {

        Queue<int> tmp = new Queue<int>(); // יצירת תור עזר

        while (!qu.IsEmpty()) // מעבר על כל התור

        {

            if (qu.Head() == num) // בדיקה האם האיבר הנוכחי שווה למספר שהתקבל כפרמטר

                qu.Remove(); // הסרה לחלוטין מהתור

            else

                tmp.Insert(qu.Remove()); // האיבר הוא לא המספר שהתקבל כפרמטר ונרצה לשחזר אותו לתור

        }

        while (!tmp.IsEmpty()) // החזרת שאר האיברים לתור

            qu.Insert(tmp.Remove());

        return qu;

    }

​

    public static int Count(Queue<int> que, int num) // O(n): n is the number of elements in the list

    {

        int count = 0;

        Queue<int> tmp = new Queue<int>(); // יצירת תור עזר

        while (!que.IsEmpty()) // מעבר על כל איברי התור

        {

            if (que.Head() == num) // בדיקה האם האיבר הנוכחי הוא המספר שהתקבל כפרמטר

                count++;

            tmp.Insert(que.Remove()); // העברה לתור עזר

        }

        while (!tmp.IsEmpty()) // שחזור התור המקורי

        {

            que.Insert(tmp.Remove());

        }

        return count;

    }

    public static Queue<int> FrequencyQueue(Queue<int> qu) // O(n^2): n is the number of elements in the list (We pass on each of the elements and run the RemoveElementsFromQueue on each of them)

    {

        Queue<int> freqQu = new Queue<int>(); // יצירת תור שכיחויות

        Queue<int> copy = CloneQueue(qu); // יצירת העתק תור (לא רוצים לשנות את התור המקורי)

        while(!copy.IsEmpty()) // סריקת כל איברי התור

        {

            int num = copy.Head(); // אחסון המספר של האיבר הנוכחי

            int count = Count(copy, num); // מציאת מספר ההופעות שלו בתור

            freqQu.Insert(num); // הכנסת המספר

            freqQu.Insert(count); // הכנסת השכיחות שלו

            copy = RemoveElementsFromQueue(copy, num); // הסרת האיברים שערכם כערך המספר של האיבר הנוכחי מהתור

        }

        return freqQu;

    }

}