Ксилофон бол модон хавтангуудыг цохиж дуугаргадаг хөгжмийн зэмсэг юм. Хавтан бүр өөрийн гэсэн тогтмол өндөрлөг бүхий эгшиг гаргадаг.

JOI-хүү \(N\) ширхэг модон хавтан бүхий ксилофон худалдаж авчээ. Хавтангууд нь зүүнээс баруун тийш \(1\)-ээс \(N\) хүртэл дугаарлагдсан байна. \(i\)-р хавтангийн эгшгийн өндөр нь \(A_i\) (\(1 \le A_i \le N\)) бөгөөд бүх хавтангуудын эгшиг хоорондоо ялгаатай. Тэрээр хамгийн бага өндөрлөгтэй (\( A_i=1 \)) хавтангийн дугаар нь хамгийн их өндөрлөгтэй (\(A_j=N\)) хавтангийн дугаараас бага (\(i < j\)) гэдгийг мэдэж байгаа.

Даалгавар

JOI-хүү аль хавтан ямар өндөртэй эгшиг гаргадгийг мэдэхгүй байгаа тул тэдгээрийг судалж тогтоохоор шийджээ. Тэрээр хэд хэдэн хавтанг зэрэг цохиж, тэдгээрээс гарч буй хамгийн өндөр ба хамгийн нам эгшгийн зөрүүг сонсож мэдэрч чадна.

Та \(10,000\)-аас илүүгүй удаа асуулга (query) ашиглан бүх хавтангийн эгшгийн өндрийг олж тогтоох ёстой.

Хэрэгжүүлэх функцүүд:

Та дараах функцийг хэрэгжүүлэх шаардлагатай:

• solve(N): Хавтангуудын өндрийг олох үндсэн функц.

Таны програм градерын (grader) дараах функцүүдийг дуудаж ашиглана:

• query(s, t): \(s\) болон \(t\) (\(1 \le s \le t \le N\)) дугаартай хавтангуудын хоорондох (тэдгээрийг оролцуулан) хамгийн их ба хамгийн бага эгшгийн өндрийн зөрүүг буцаана.
• answer(i, a): \(i\)-р хавтангийн өндөр \(A_i\) нь \(a\) болохыг хариулна.
  • Хавтан бүрийн хувьд энэ функцийг яг нэг удаа дуудах ёстой.

Хязгаарлалтууд:

Бүх дэд бодлогуудад дараах нөхцөл биелнэ:

• \(1 \le A_i \le N\).
• \(A_i \ne A_j\) (\(i \ne j\) үед) ~.
• \(A_i = 1\) ба \(A_j = N\) байх \(i, j\) дугааруудын хувьд \(i < j\) байна.

Дэд бодлогууд

• Дэд бодлого 1 (11 оноо): \(2 \le N \le 100\).
• Дэд бодлого 2 (36 оноо): Асуулга бүрийн \(2 \le N \le 1,000\).
• Дэд бодлого 3 (53 оноо): \(2 \le N \le 5,000\).

Харилцааны жишээ (\(N=5\))

Хэрэв эгшгийн өндрүүд \((A_1, A_2, A_3, A_4, A_5) = (2, 1, 5, 3, 4)\) бол:

• query(1, 5) дуудахад \(5-1 = 4\)-ийг буцаана.
• answer(1, 2) гэж хариулна.
• query(3, 5) дуудахад \(5-3 = 2\)-ыг буцаана.
• Бусад хавтангуудыг answer(i, a) ашиглан хариулж дуусгана.

Нэмэлт материалууд

• data.zip татах