C. Овоолгын үйлдүүд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Петя саяхан "Хоёртын овоолго" нэртэй өгөгдлийн бүтцийг судласан.

Овоолго нь доорх үйлдлүүдийг зөвшөөрөн ажиллаж байна:

  • овоолгоруу өгөгдсөн тоог оруулах;
  • овоолго дахь хамгийн бага элементийн утгыг авах;
  • овоолгоос хамгийн бага элементийг гаргах;

Иймд хугацааны дурын мөчид овоолго хэд хэдэн бүхэл тоон утга агуулна (хоосон байж болно), эдгээрийн зарим нь тэнцүү байж болно.

Энэ өгөгдлийн бүтцийг илүү сайн сурахын тулд Петя хоосон овоолго авсан ба үүн дээрээ хэд хэдэн үйлдэл хийсэн. Мөн тэр бүх үйлдлүүдээ үр дүнтэй нь хамт өөрийн тэмдэглэлдээ дараах форматтайгаар бичсэн:

  • $insert$ $x$ -- овоолгоруу $x$ утгатай элемент нэмсэн;
  • $getMin$ $x$ -- овоолго дахь хамгийн бага утгатай элемент $x$ байсан;
  • $removeMin$ -- овоолгоос хамгийн бага элементийг гаргасан (хэрвээ олон элемент байвал нэгийг нь л гаргана).

Бүх үйлдэл зөв байсан буюу $getMin$ эсвэл $removeMin$ үйлдлүүдийг хийхэд овоолгод ядаж нэг элемент байсан.

Петя үдийн хоол идэхээр хол байх хойгуур түүний дүү Вова түүний өрөөнд ороод Петягийн тэмдэглэлээс хэдэн хуудсыг авч цаасан онгоц хийхэд ашигласан.

Вова Петягийн үйлдлүүдийн дарааллыг дэс дараалалгүй болгосон байх вий гэж санаа зовж байна. Жишээлбэл тэмдэглэл дээр тэмдэглэсэн дарааллын дагуу үйлдлүүдийг нэг нэгээр нь гүйцэтгэхэд $getMin$ үйлдлийн үр дүн Петягийн бичсэнээс ялгаатай байж болно мөн зарим $getMin$ эсвэл $removeMin$ үйлдлүүд нь буруу буюу эдгээр үйлдлийг гүйцэтгэх явцад овоолго хоосон байж болох юм.

Харин одоо Вова гарах үйлдлүүдийн дараалал зөв байхаар тэмдэглэлд зарим шинэ үйлдлүүдийг тэмдэглэхээр шийдсэн. Өөрөөр $getMin$ үйлдэл бүрийн хувьд гарах хариу нь тэмдэглэл дээрх бичлэгтэй тэнцүү байх мөн $getMin$ болон $removeMin$ үйлдлүүдийг гүйцэтгэх үед овоолго хоосон биш байна гэсэн үг. Петя хэзээ ч ирж болох тул Вова үүнийг боломжит хамгийн хурднаар хийхийг хүсч байна. Тэр таныг одоо байгаа тэмдэглэлд боломжит хамгийн бага тооны үйлдлийг тэмдэглэхийг хүсч байна. Дурын тооны үйлдлүүд тэмдэглэлийн эхэнд болон дурын хоёр үйлдлийн хооронд мөн тэмдэглэлийн төгсгөлд нэмэгдэж болно гэдгийг санаарай.

Оролт

Оролтын эхний мөрөнд зөвхөн бүхэл тоон утга $n$ ($1 ≤ n ≤ 100 000$) байх буюу Петягийн тэмдэглэлд үлдсэн бичлэгүүдийн тоо юм.

Дараагийн $n$ мөр бүрт одоо байгаа тэмдэглэл дахь бичлэгүүдийг тэдний хийгдсэн дарааллаар нь тодорхойлно. Бодлогын нөхцөлд тодорхойлогдсон форматыг ашиглана. Оролтын бүх тоонууд бүхэл тоон утгууд байх ба үнэмлэхүй утгаараа $10^{9}$-с ихгүй байна.

Гаралт

Гаралтын эхний мөрөнд нэг бүхэл тоон утга $m$ буюу үйлдлүүдийн өөрчлөгдсөн дараалал дахь бичлэгүүдийн боломжит хамгийн бага тоо юм.

Дараагийн $m$ мөрөнд зөв болгосон бичлэгүүдийн дарааллыг нэг мөрөнд нэг үйлдлийг хийгдсэн дарааллаар нь оролтын форматаар (бодлогын нөхцөлд тодорхойлсон форматаар) хэвлэнэ. Гаралтын бүх тоонууд бүхэл тоон утгууд байх ба үнэмлэхүй утгаараа $10^{9}$-с ихгүй байна.

Оролтын үйлдлүүдийн дараалал нь гаралтын үйлдлүүдийн дарааллын дэд дараалал байх ёстой.

Мөн $1 000 000$-с ихгүй үйлдлээс тогтох зөв хариулт байх нь тодорхой.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
2
insert 3
getMin 4
Гаралт
4
insert 3
removeMin
insert 4
getMin 4
Оролт
4
insert 1
insert 1
removeMin
getMin 2
Гаралт
6
insert 1
insert 1
removeMin
removeMin
insert 2
getMin 2

Тэмдэглэл

Эхний жишээн дээр овоолгоруу $3$ тоог оруулсны дараа хамгийн бага тоо нь $3$ байна. Хамгийн эхний $getMin$ үйлдлийн үр дүнг $4$-тэй тэнцүү байлгахын тулд эхлээд овоолгоос $3$ тоог устгаад дараа нь $4$ тоог нэмэх хэрэгтэй.

Хоёр дахь жишээн дээр $1$ тоо хоёр удаа орсон ба үүнтэй адилаар хоёр удаа устгагдах ёстой.

Сэтгэгдлүүдийг ачааллаж байна...