// 31-5-4 Otesánek ve vývařovně
// Autor: Jirka Setnička
#include<stdio.h>
#include<stdlib.h>

#define OKENKO -1

/* Formát vstupu: Na prvním řádku číslo N udávající, kolik událostí bude
následovat. Na dalších N řádcích poté buď znak 'P' znamenající příchod a nebo
znak 'O' následovaný mezerou a číslem znamenající odchod i-tého vesničana
(indexujeme od nuly).

Formát výstupu: Pro každý příchod 'P' vypíšeme pozici, kam se vesničan posadí,
jako desetinné číslo mezi 0 a 1.

    Ukázkový vstup:
    10
    P
    P
    P
    P
    O 1
    P
    P
    O 3
    P
    O 4

    Ukázkový výstup:
    0.500000
    0.250000
    0.750000
    0.125000
    0.312500
    0.875000
    0.156250
*/

typedef struct {
	double zacatek;
	double delka;
	int levy_stravnik;
	int pravy_stravnik;
} t_misto;

typedef struct {
	int leve_misto;
	int prave_misto;
} t_stravnik;

////////////////////////////////////////////////////////////////////////////////
// Objekt, který si pamatuje všechno o naší haldě (budeme ho předávat funkcím)
typedef struct {
	int velikost;
	t_misto* mista;
	t_stravnik* stravnici;
} t_halda;

// Funkce pro práci s haldou:
void halda_update_link(t_halda* h, int i) {
	if (h->mista[i].levy_stravnik != OKENKO)
		h->stravnici[h->mista[i].levy_stravnik].prave_misto = i;
	if (h->mista[i].pravy_stravnik != OKENKO)
		h->stravnici[h->mista[i].pravy_stravnik].leve_misto = i;
}

void halda_swap(t_halda* h, int a, int b) {
	if (a == b) return;
	// Swap
	t_misto temp = h->mista[a];
	h->mista[a] = h->mista[b];
	h->mista[b] = temp;
	// Oprava odkazů z pole stravnici po prohození
	halda_update_link(h, a);
	halda_update_link(h, b);
}

void halda_bublej_nahoru(t_halda* h, int i) {
	if (i == 0) return;
	int otec = (i - 1) / 2;
	if (h->mista[otec].delka < h->mista[i].delka) {
		halda_swap(h, i, otec);
		halda_bublej_nahoru(h, otec);
	}
}

void halda_bublej_dolu(t_halda* h, int i) {
	int prvni = 2*i + 1;
	int druhe = 2*i + 2;
	if (prvni >= h->velikost) return; // Pokud nemáme děti, není kam bublat

	double delka = h->mista[i].delka;
	int prohod;
	if (druhe >= h->velikost) {
		// Jenom jedno dítě
		if (h->mista[prvni].delka < delka) return; // Pokud je menší, je vše v pohodě
		else prohod = prvni;
	} else {
		// Máme obě děti - pokud jsou obě menší, tak nic, jinak se prohodíme za to větší z nich
		if (h->mista[prvni].delka < delka && h->mista[druhe].delka < delka) return;
		else if (h->mista[prvni].delka > h->mista[druhe].delka) prohod = prvni;
		else prohod = druhe;
	}

	halda_swap(h, i, prohod);
	halda_bublej_dolu(h, prohod);
}

void halda_insert(t_halda* h, t_misto misto) {
	int index = h->velikost;
	h->mista[index] = misto;
	h->velikost++;
	halda_update_link(h, index); // odkazy ze strávníků
	halda_bublej_nahoru(h, index);
}

t_misto halda_delete(t_halda* h, int i) {
	// 1. Prohodíme prvek na konec a smažeme ho (posuneme konec haldy)
	h->velikost--;
	halda_swap(h, i, h->velikost);
	// 2. Zabubláme prohozený prvek, zkusíme projistotu oba směry
	halda_bublej_dolu(h, i);
	halda_bublej_nahoru(h, i);
	return h->mista[h->velikost];
}

////////////////////////////////////////////////////////////////////////////////

int main() {
	// 1. Načteme N a pořídíme si haldu velkou N, ve které si budeme
	// pamatovat volné úseky. Také si bude pamatovat pole strávníků kvůli
	// zpětným odkazům na volné úseky (předpokládáme, že dvě pole velká N se
	// nám do paměti ještě vejdou).
	int N;
	scanf("%d\n", &N);

	t_halda halda = {
		.velikost = 0,
		.mista = malloc(sizeof(t_misto) * N),
		.stravnici = malloc(sizeof(t_stravnik) * N),
	};

	// 2. Do haldy na začátku vložíme jedno volné místo, -1 nám značí paní
	// na koncích
	halda_insert(&halda, (t_misto){0, 1, OKENKO, OKENKO});

	// 3. Postupně zpracováváme události
	char typ;
	int stravniku = 0;
	int index;
	for (int i = 0; i < N; i++) {
		scanf("%c", &typ);
		if (typ == 'P') {
			index = stravniku++;
			scanf("\n"); // Aby další čtení nenačetlo newline
			// 1. Vytáhneme největší volné místo a posadíme nově příchozího doprostřed
			t_misto nejvetsi = halda_delete(&halda, 0);
			double prostredek = nejvetsi.zacatek + nejvetsi.delka/2;

			// 2. Vložíme dvě nová volná místa
			halda_insert(&halda, (t_misto){nejvetsi.zacatek, nejvetsi.delka/2, nejvetsi.levy_stravnik, index});
			halda_insert(&halda, (t_misto){prostredek, nejvetsi.delka/2, index, nejvetsi.pravy_stravnik});

			// 3. Vypíšeme místo, kam si má příchozí sednout
			printf("%f\n", prostredek);
		} else if (typ == 'O') {
			scanf("%d\n", &index);
			// 1. Vytáhneme z haldy obě sousední volná místa
			t_misto a = halda_delete(&halda, halda.stravnici[index].leve_misto);
			t_misto b = halda_delete(&halda, halda.stravnici[index].prave_misto);

			// 2. Vložíme spojené místo opět do haldy
			halda_insert(&halda, (t_misto){a.zacatek, a.delka + b.delka, a.levy_stravnik, b.pravy_stravnik});
		}
	}
}