Принята

#include <iostream>
#include <vector>


enum sort_type
{
    heap_max = 0,
    heap_min = 1
};

struct heap_elements
{
    int value;
    int own_ID;
};

bool operator<(const heap_elements& a, const heap_elements& b)
{
    return (a.value < b.value);
}

class Heap
{
    std::vector<struct heap_elements> h;
    int heap_size;

public:
    Heap();
    bool isempty();
    heap_elements get_top();
    void siftup(int sort_type, int pos, std::vector<int>& ID_to_Index);
    void siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index);
    void my_swap(int i, int j, std::vector<int>& ID_to_Index);
    void add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index);
    void delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index);
};

Heap::Heap()
{
    std::vector<struct heap_elements> h;
    heap_size = 0;
}

heap_elements Heap::get_top()
{
    return h[0];
}

bool Heap::isempty()
{
    if (heap_size == 0)
        return true;
    return false;
}

void Heap::my_swap(int i, int j, std::vector<int>& ID_to_Index)
{
    heap_elements buff;
    buff = h[i];
    h[i] = h[j];
    h[j] = buff;

    ID_to_Index[h[i].own_ID] = i; // На местах в этом массиве лежат айди этой кучи все ок
    ID_to_Index[h[j].own_ID] = j;
}

void Heap::siftup(int sort_type, int pos, std::vector<int>& ID_to_Index)
{
    int curr = pos;
    int parent = (curr - 1) / 2;
    while (curr > 0 & parent >= 0)
    {
        if (sort_type == heap_max & h[parent] < h[curr])
            my_swap(parent, curr, ID_to_Index);

        if (sort_type == heap_min & h[curr] < h[parent])
            my_swap(parent, curr, ID_to_Index);

        curr = parent;
        parent = (curr - 1) / 2;
    }
}


void Heap::siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index)
{

    int parent, max_child, min_child;

    int curr = pos;
    int child_l = 2 * curr + 1;
    int child_r = 2 * curr + 2;

    while (child_l < heap_size)
    {
        if (sort_type == heap_max)
        {
            if (child_l == heap_size - 1)
                max_child = child_l;
            else if (h[child_r] < h[child_l])
                max_child = child_l;
            else
                max_child = child_r;

            if (h[curr] < h[max_child])
                my_swap(curr, max_child, ID_to_Index);

            curr = max_child;
            child_l = 2 * curr + 1;
            child_r = 2 * curr + 2;
        }

        if (sort_type == heap_min)
        {

            if (child_l == heap_size - 1)
                min_child = child_l;
            else if (h[child_r] < h[child_l])
                min_child = child_r;
            else
                min_child = child_l;


            if (h[min_child] < h[curr])
            {
                my_swap(curr, min_child, ID_to_Index);
            }
            curr = min_child;
            child_l = 2 * curr + 1;
            child_r = 2 * curr + 2;
        }
    }
}


void Heap::add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index)
{
    heap_elements vertex;
    vertex.value = value;
    vertex.own_ID = ID;

    h.push_back(vertex);


    if (ID < ID_to_Index.size())
    {
        ID_to_Index[ID] = heap_size;
    }
    else
    {
        ID_to_Index.push_back(heap_size); // должно быть общее у двух куч
    }
    heap_size++;
    siftup(sort_type, heap_size - 1, ID_to_Index);
}

void Heap::delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index)
{

    int pos = ID_to_Index[ID];


    my_swap(pos, heap_size - 1, ID_to_Index); // Можно не делать свап
    h.pop_back();
    heap_size--;
    ID_to_Index[ID] = -1; // мб убрать

    int parent = (pos - 1) / 2;

    if (sort_type == heap_min)
    {
        if (h[pos] < h[parent])
            siftup(sort_type, pos, ID_to_Index);
        else
            siftdown(sort_type, pos, ID_to_Index);
    }

    if (sort_type == heap_max)
    {
        if (h[parent] < h[pos])
            siftup(sort_type, pos, ID_to_Index);
        else
            siftdown(sort_type, pos, ID_to_Index);
    }
}



int main()
{


    Heap heap_one;
    Heap heap_two;

    std::vector<int> ID_to_Index;
    int NumberHeap;
    int curr_ID = 0;
    char c;

    int N, M, K, ID, ID_root_one, root_two_ID, ID_root_two, count = 1;
    std::cin >> N;
    std::cin >> M;
    std::cin >> K;
    int R = 0, L = 0;
    int a[N];
    for (int j = 0; j < N; ++j)
        std::cin >> a[j];

    int ID_to_HeapNumber[N];

    heap_one.add(heap_max, curr_ID, a[0], ID_to_Index);
    ID_to_HeapNumber[curr_ID] = 1;
    curr_ID++;


    for (int i = 0; i < M; ++i)
    {

        std::cin >> c;

        if (c == 'R')
        {
            count++;
            R++;


            if (count < K)
            {


                heap_one.add(heap_max, curr_ID, a[R], ID_to_Index);
                ID_to_HeapNumber[curr_ID] = 1;
                curr_ID++;

                std::cout << -1 << std::endl;
            }

            if (count == K)
            {


                heap_one.add(heap_max, curr_ID, a[R], ID_to_Index);
                ID_to_HeapNumber[curr_ID] = 1;
                curr_ID++;

                std::cout << heap_one.get_top().value << std::endl;
            }

            if (count > K)
            {


                if (a[R] > heap_one.get_top().value)
                {

                    heap_two.add(heap_min, curr_ID, a[R], ID_to_Index);
                    ID_to_HeapNumber[curr_ID] = 2;
                    curr_ID++;
                    std::cout << heap_one.get_top().value << std::endl;
                }

                if (a[R] <= heap_one.get_top().value)

                {


                    heap_elements root_one, root_two;

                    // Запоминаю корень 1 кучи
                    root_one = heap_one.get_top();
                    ID_root_one = root_one.own_ID;

                    //  удаляю корень 1 кучи из 1 кучи
                    heap_one.delete_vertex(heap_max, ID_root_one, ID_to_Index);


                    //  Добавляю корень 1 кучи во 2 кучу не меняя ID
                    heap_two.add(heap_min, ID_root_one, root_one.value, ID_to_Index);
                    ID_to_HeapNumber[ID_root_one] = 2;


                    // Добавляю в 1 кучу a[R]  меняя айди
                    heap_one.add(heap_max, curr_ID, a[R], ID_to_Index);
                    ID_to_HeapNumber[curr_ID] = 1;
                    curr_ID++;


                    std::cout << heap_one.get_top().value << std::endl;
                }
            }
        }
        else
        {
            L++;
            count--;


            ID = L - 1;
            NumberHeap = ID_to_HeapNumber[ID];


            // Если лежит в куче1 то удаляем там, иначе во 2
            if (NumberHeap == 1)
                heap_one.delete_vertex(heap_max, ID, ID_to_Index);
            else
                heap_two.delete_vertex(heap_min, ID, ID_to_Index);


            if (count >= K)
            {


                // Если удалили из 2 кучи, то первая не пострадала и просто принтим
                if (NumberHeap == 2)
                {
                    std::cout << heap_one.get_top().value << std::endl;
                }

                else
                {

                    // Запоминаю вершину кучи2
                    heap_elements root_two = heap_two.get_top();
                    root_two_ID = root_two.own_ID;


                    // Удаляем вершину кучи2, т.к. теперь она в куче1
                    heap_two.delete_vertex(heap_min, root_two_ID, ID_to_Index);


                    // Добавляем вершину кучи2 в кучу1  не меняя индекс чтобы стало K штук
                    heap_one.add(heap_max, root_two_ID, root_two.value, ID_to_Index);
                    ID_to_HeapNumber[root_two_ID] = 1;

                    std::cout << heap_one.get_top().value << std::endl;
                }
            }
            else
            {
                std::cout << -1 << std::endl;
            }
        }
    }


    return 0;
}