#include <stdio.h>

typedef enum ENUM_ORDEM {CRESCENTE, DECRESCENTE, DESORDENADA} ordem_t;

void busca_binaria(int vet[], int ini, int fim, int ra, ordem_t ordem) {
    int meio = (ini+fim)/2;

    /* vetor vazio não possui elementos: */
    if (fim < ini) {
        printf("\n%d nao esta na lista!", ra);
        return;
    }

    printf("%d ", meio);

    /* testa se o elemento procurado é o do meio */
    if (vet[meio] == ra) {
        printf("\n%d esta na posicao: %d", ra, meio);
        return;
    }
    
    /* se não é o do meio, é maior ou menor do que o do meio 
     * nesse caso, testamos o tipo da ordenação da lista para saber
     * "para que lado" ir na busca */
    if (ordem == CRESCENTE) {
        if (vet[meio] > ra)
            return busca_binaria(vet, ini, meio-1, ra, ordem);
        return busca_binaria(vet, meio+1, fim, ra, ordem);
    } else {
        if (vet[meio] < ra)
            return busca_binaria(vet, ini, meio-1, ra, ordem);
        return busca_binaria(vet, meio+1, fim, ra, ordem);
    }
}

/* retorna a posição de um elemento no vetor, se ele existir
 * retorna -1 se não existir */
int encontra_pos(int vet[], int ini, int fim, int ra, ordem_t ordem) {
    int i, pos;
    pos = -1;
    for (i = ini; i <= fim; i++) {
        if (vet[i] == ra)
            return pos;
    }
    return -1;
}

int main() {
    int i, j, n;
    int aux, pos;
    int lista[150];
    char op;
    ordem_t ordenacao = DESORDENADA;

    /* lendo quantidade de alunos e RA de cada um: */
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &lista[i]);
    }

    do {
        scanf("%c", &op);
        switch(op) {
            case 'p':
                /* Operação de impressão da lista atual */
                if (n > 0) {
                    for (i = 0; i < n; i++)
                        printf("%d ", lista[i]);
                    printf("\n");
                }
                break;

            case 'c':
                /* Ordenar de forma crescente a lista
                 * Vamos usar Selection Sort */
                for (i = 0; i < n-1; i++) {
                    pos = i;
                    /* procurando o menor elemento a partir da posição i */
                    for (j = i+1; j < n; j++) {
                        if (lista[j] < lista[pos])
                            pos = j;
                    }
                    /* troca o menor elemento com o da posição i */
                    aux = lista[pos];
                    lista[pos] = lista[i];
                    lista[i] = aux;
                }
                ordenacao = CRESCENTE;
                break;

            case 'd':
                /* Ordenar de forma decrescente a lista
                 * Vamos usar Selection Sort */
                for (i = 0; i < n; i++) {
                    pos = i;
                    /* procurando o maior elemento a partir da posição i */
                    for (j = i+1; j< n; j++) {
                        if (lista[j] > lista[pos])
                            pos = j;
                    }
                    /* troca o maior elemento com o da posição i */
                    aux = lista[pos];
                    lista[pos] = lista[i];
                    lista[i] = aux;
                }
                ordenacao = DECRESCENTE;
                break;

            case 'b':
                /* Fazer busca na lista apenas se ela estiver ordenada de alguma forma */
                scanf("%d", &aux);
                if (ordenacao == DESORDENADA)
                    printf("Vetor nao ordenado!");
                else
                    busca_binaria(lista, 0, n-1, aux, ordenacao);
                printf("\n");
                break;

            case 'i':
                /* Inserir aluno novo apenas se houver espaço na turma */
                scanf("%d", &aux);

                if (n == 150) {
                    printf("Limite de vagas excedido!\n");
                    break;
                }

                /* se o aluno já estiver na turma, não insere */
                pos = encontra_pos(lista, 0, n-1, aux, ordenacao);
                if (pos != -1) {
                    printf("Aluno ja matriculado na turma!\n");
                    break;
                }

                /* se o aluno não estiver na turma e a lista for desordenada, basta inserir no fim
                 * se a lista for ordenada, precisamos "abrir espaço" para inserir o aluno "*/
                if (ordenacao == DESORDENADA) {
                    lista[n] = aux;
                } else if (ordenacao == CRESCENTE) {
                    /* encontrar posição onde o aluno deve ser inserido: 
                     * entre o valor menor do que ele e o valor maior do que ele */
                    pos = 0;
                    while (pos < n && lista[pos] < aux)
                        pos++;
                    for (i = n-1; i >= pos; i--)
                        lista[i+1] = lista[i];
                    /* e insere o aluno na posição pos */
                    lista[pos] = aux;
                } else { /* ordenacao == DECRESCENTE */

                }
                /* incrementa o total de alunos */
                n++;
                break;

            case 'r':
                /* Remover aluno da lista apenas se ele existir */
                scanf("%d", &aux);

                if (n == 0) {
                    printf("Nao ha alunos cadastrados na turma!\n");
                    break;
                }

                /* se o aluno não existir, IMPRIMIR MENSAGEM */

    
                break;

            case 's':
                break;
        }
    } while(op != 's');

    return 0;
}