#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Stack {
    int *data, cap, top1, top2, max;
};

struct Stack InitStack(int n)
{
    struct Stack s;
    int *d = (int*)malloc(n * sizeof(int));
    s.data = d;
    s.cap = n;
    s.top1 = 0;
    s.top2 = n - 1;
    s.max = -2000000000;
    return s;
}

int StackEmpty1(struct Stack s)
{
    return s.top1 == 0;
}

int StackEmpty2(struct Stack s)
{
    return s.top2 == s.cap - 1;
}

void Push1(struct Stack s, int x)
{
    if (s.top2 < s.top1) printf("Переполнение\n");
    s.data[s.top1] = x;
    s.top1++;
}

void Push2(struct Stack s, int x)
{
    if (s.top2 < s.top1) printf("Переполнение\n");
    s.data[s.top2] = x;
    s.top2--;
}

int Pop1(struct Stack s)
{
    if (StackEmpty1(s)) printf("NULL\n");
    s.top1--;
    return s.data[s.top1];
}

int Pop2(struct Stack s)
{
    if (StackEmpty2(s)) printf("NULL\n");
    s.top2++;
    return s.data[s.top2];
}

struct Stack InitQueue(int n)
{
    return InitStack(n);
}

int QueueEmpty(struct Stack s)
{
    return (StackEmpty1(s) && StackEmpty2(s));
}

struct Stack Enqueue(struct Stack s, int x)
{
    Push1(s, x);
    s.top1++;
    if (x > s.max) s.max = x;
    return s;
}

int *Dequeue(struct Stack s)
{
    int cur = 0;
    int *res = (int*)malloc(2 * sizeof(int));
    if (StackEmpty2(s)) {
        while (!(StackEmpty1(s))) {
            Push2(s, Pop1(s));
            s.top1--;
            s.top2--;
            cur++;
        }
    }
    res[0] = cur;
    res[1] = Pop2(s);
    return res;
}

int main()
{
    int j, i, n, x, *cur;
    char ss[8];
    scanf("%d\n", &n);
    struct Stack s = InitQueue(2 * n);
    for (i = 0; i < n; i++) {
        scanf("%s", ss);
        if (0 == strcmp(ss, "ENQ")) {
            scanf(" %d", &x);
            s = Enqueue(s, x);
        }
        if (0 == strcmp(ss, "EMPTY")) {
            if (QueueEmpty(s)) printf("true\n");
            else printf("false\n");
        }
        if (0 == strcmp(ss, "DEQ")) {
            cur = Dequeue(s);
            s.top1 -= cur[0];
            s.top2 -= cur[0];
            s.top2++;
            if (cur[1] == s.max) {
                s.max = -2000000000;
                for (j = s.top2 + 1; j < s.cap; j++) {
                    if (s.data[j] > s.max) s.max = s.data[j];
                }
            }
            printf("%d\n", cur[1]);
            free(cur);
        }
        if (0 == strcmp(ss, "MAX")) {
            printf("%d\n", s.max);
        }
        if (i != n - 1) scanf("\n");
    }
    free(s.data);
    return 0;
}