#include <iostream>
#include <vector>
#include <string>

enum QueueCodes { EmptyHead, Success };
enum HeapCodes { EmptyHeap, Successfuly };

template <typename T>
class Queue {
private:
struct Node {
T value;
Node* next_node;
Node* previous_node;
};

Node* head_;
Node* tail_;
size_t size_;

public:
Queue();
~Queue();

bool Empty();
size_t GetSize();
std::pair<QueueCodes, T> GetTail();

void Push(T value);
std::pair<QueueCodes, T> Pop();
std::pair<QueueCodes, T> PopFront();

void DeleteQueue();
};

template <typename T>
class BinHeap {
public:
BinHeap();
~BinHeap();

void ExtractMin();
void DecreaseKey(void* target, T delta);

std::pair<HeapCodes, T> GetMin();
void* Insert(T value);

private:
struct Node {
T value;
Node* parent;
Node* left_child;
Node* right_child;

void SiftUp();
void SiftDown();
};

Queue<Node*> leafs_;
Node* head_;
size_t size_;
};

template <typename T>
void DoOperation(BinHeap<T>& heap, std::vector<void*>& nodes, std::string operation) {
if (operation == "insert") {
T value;

std::cin >> value;

nodes.push_back(heap.Insert(value));
} else if (operation == "getMin") {
std::cout << heap.GetMin().second << "\n";

nodes.push_back(nullptr);
} else if (operation == "extractMin") {
heap.ExtractMin();
nodes.push_back(nullptr);
} else {
int ptr;
int delta;

std::cin >> ptr >> delta;

heap.DecreaseKey(nodes[ptr - 1], delta);
nodes.push_back(nullptr);
}
}

int main() {
std::vector<void*> nodes;
BinHeap<int> heap;
int n;

std::cin >> n;

while (n-- != 0) {
std::string operation;

std::cin >> operation;

DoOperation<int>(heap, nodes, operation);
}
}

template <typename T>
Queue<T>::Queue() {
head_ = nullptr;
tail_ = nullptr;
size_ = 0;
}

template <typename T>
Queue<T>::~Queue() {
DeleteQueue();
}

template <typename T>
bool Queue<T>::Empty() {
return head_ == nullptr;
}

template <typename T>
size_t Queue<T>::GetSize() {
return size_;
}

template <typename T>
std::pair<QueueCodes, T> Queue<T>::GetTail() {
if (tail_ != nullptr) {
return {Success, tail_->value};
}
return {EmptyHead, T()};
}

template <typename T>
void Queue<T>::Push(T value) {
Node* new_head = new Node({value, head_, nullptr});
if (tail_ == nullptr) {
tail_ = new_head;
}
if (head_ != nullptr) {
head_->previous_node = new_head;
}

head_ = new_head;
++size_;
}

template <typename T>
std::pair<QueueCodes, T> Queue<T>::Pop() {
if (tail_ == nullptr) {
return {EmptyHead, T()};
} else if (tail_ == head_) {
T value = tail_->value;
delete tail_;
tail_ = nullptr;
head_ = nullptr;
--size_;
return {Success, value};
}

T value = tail_->value;
tail_ = tail_->previous_node;
delete tail_->next_node;
--size_;
return {Success, value};
}

template <typename T>
std::pair<QueueCodes, T> Queue<T>::PopFront() {
if (head_ == nullptr) {
return {EmptyHead, T()};
} else if (tail_ == head_) {
T value = tail_->value;
delete tail_;
tail_ = nullptr;
head_ = nullptr;
--size_;
return {Success, value};
}

T value = head_->value;
head_ = head_->next_node;
delete head_->previous_node;

return {Success, value};
}

template<typename T>
void Queue<T>::DeleteQueue() {
while (head_) {
Node* tmp = head_;
head_ = head_->next_node;
delete tmp;
}
tail_ = nullptr;
size_ = 0;
}


template <typename T>
BinHeap<T>::BinHeap() {
head_ = nullptr;
size_ = 0;
}

template <typename T>
BinHeap<T>::~BinHeap() {
while (!leafs_.Empty()) {
Node* leaf = leafs_.Pop().second;
delete leaf;
}
}

template <typename T>
void BinHeap<T>::ExtractMin() {
if (size_ == 1) {
delete head_;
size_ = 0;
head_ = nullptr;
} else {
Node* leaf = leafs_.Pop().second;
head_->value = leaf->value;

Node* parent = leaf->parent;

if (parent->left_child == leaf) {
parent->left_child = nullptr;
delete leaf;
} else {
parent->right_child = nullptr;
delete leaf;
}

head_->SiftDown();
}
}

template <typename T>
void BinHeap<T>::DecreaseKey(void *target, T delta) {
Node* target_node = (Node*)target;
target_node->value -= delta;
target_node->SiftUp();
}

template <typename T>
std::pair<HeapCodes, T> BinHeap<T>::GetMin()
{
if (head_ == nullptr) {
return {EmptyHeap, T()};
} else {
return {Successfuly, head_->value};
}
}

template <typename T>
void* BinHeap<T>::Insert(T value)
{
++size_;

if (head_ == nullptr) {
head_ = new Node{value, nullptr, nullptr, nullptr };
leafs_.Push(head_);

return (void*)head_;
}

Node* leaf = leafs_.GetTail().second;

if (leaf->left_child == nullptr) {
leaf->left_child = new Node{value, leaf, nullptr, nullptr };
leafs_.Push(leaf->left_child);

leafs_.Pop();

leaf->left_child->SiftUp();

return (void*)leaf->left_child;
}

leaf->right_child = new Node{value, leaf, nullptr, nullptr };
leafs_.Push(leaf->right_child);

leafs_.Pop();

leaf->right_child->SiftUp();

return (void*)leaf->right_child;
}

template <typename T>
void BinHeap<T>::Node::SiftUp() {
if (parent != nullptr && parent->value > value) {
T temporary_value = value;
value = parent->value;
parent->value = temporary_value;

parent->SiftUp();
}
}

template <typename T>
void BinHeap<T>::Node::SiftDown() {
if (left_child != nullptr && right_child != nullptr) {
Node* min_neighbour = (left_child->value <= right_child->value) ? left_child:right_child;

if (min_neighbour->value < value) {
T temporary_value = value;
value = min_neighbour->value;
min_neighbour->value = temporary_value;

min_neighbour->SiftDown();
}
} else if ((left_child == nullptr) != (right_child == nullptr)) {
Node* min_neighbour = (left_child != nullptr) ? left_child:right_child;

if (min_neighbour->value < value) {
T temporary_value = value;
value = min_neighbour->value;
min_neighbour->value = temporary_value;

min_neighbour->SiftDown();
}
}
}