Палиндром
Бодлогын өгүүлбэр
Тэмүүжин хүү ээжтэйгээ хамт “Бурхан халдун” цэцэрлэгт хүрээлэнд байнга зугаалдаг. “Бурхан халдун” цэцэрлэгт хүрээлэн нь геометрийн нарийн хэлбэр, шулуун шугамуудын дагуу мод бутаа тарьж, хэлбэржүүлсэн алдартай, сонгодог загварын цэцэрлэгт хүрээлэн юм.
“Бурхан халдун” цэцэрлэгт хүрээлэнгийн нэгэн онцлох хэсэг нь Кубэн бутнуудын гудамж юм. Кубэн бут гэдэг нь хоорондоо ижил хэмжээтэй, куб хэлбэрийн хэд хэдэн хэсэг нэг нэгнийхээ дээр давхарлан байрласан ургамал юм. Кубэн бутнуудын гудамжинд нийт n ширхэг бут нэг эгнээнд таригдсан байдаг. Тэмүүжин төрөлхийн геометрт дуртай учраас энэ гудамжаар зугаалах дуртай. Тэрээр гудамжинд анх удаа очихдоо бут бүрийн өндрийг тэмдэглэж авсан. Бутны өндөр гэдэг нь тухайн бутыг бүрдүүлж буй куб хэсгүүдийн тоо юм. Тэмүүжин Кубэн бутнуудын гудамжинд тэгш хэмтэй хэсгийг харах онцгой дуртай. Тиймээс тэрээр өндрүүд нь шаталсан палиндром үүсгэх бутнуудын дарааллыг хайдаг.
Шаталсан палиндром гэдэг нь сондгой урттай бутнуудын дараалал бөгөөд дараах шинж чанартай байна:
- Дарааллын эхний хагаст бут бүрийн өндөр өмнөх бутныхаас нэгээр их байна.
- Дарааллын голд хамгийн өндөртэй ганц бут байрлана.
- Үүний дараа бутнуудын өндөр дарааллын төгсгөл хүртэл нэг нэгээр буурна.
- Дарааллын голд байх өндөр бутнаас ижил зайд байрлах бутнуудын өндөр хоорондоо тэнцүү байна.
Жишээлбэл [1,2,3,2,1] нь шаталсан палиндром мөн. Харин [1,2], [1,5,2] нь шаталсан палиндром биш юм.
Бүх шаталсан палиндром дотроос Тэмүүжин хамгийн уртыг нь олохыг хүсэж байна. Тэмүүжин сар бүр цэцэрлэгт хүрээлэнд ирдэг. “Бурхан халдун” цэцэрлэгийн цэцэрлэгчид кубэн бутнуудыг үргэлж ижил харагдуулахын тулд тайрахыг хичээдэг боловч Тэмүүжин цэцэрлэгт хүрээлэнд ирэх бүрд бутнуудын аль нэгнийх нь өндөр өөрчлөгддөгийг анзаарчээ. Иймээс хамгийн урт шаталсан палиндромын урт өөрчлөгдөж болно.
Тэмүүжин одоогоор бага учраас энэ бодлогыг өөрөө бодож чадахгүй байна. Тиймээс түүнд цэцэрлэгт хүрээлэнд анх очих үеийн болон дараагийн бүх удаагийн очилтын дараах хамгийн урт шаталсан палиндромын уртыг олоход нь тусална уу.
Оролтын формат
Эхний мөрөнд гудамжинд байгаа бутны тоо болох n (1≤n≤105) бүхэл тоо өгөгдөнө.
Хоёр дахь мөрөнд бутнуудын анхны өндрийг илэрхийлэх n ширхэг ai (1≤ai≤107) бүхэл тоо өгөгдөнө.
Гурав дахь мөрөнд Тэмүүжин цэцэрлэгт хүрээлэнд ирэх долоо хоногийн тоо болох q (1≤q≤105) бүхэл тоо өгөгдөнө.
Дараагийн q мөр тус бүрд хоёр бүхэл тоо i,x өгөгдөнө. Энэ нь i-р бутны өндөр x болж өөрчлөгдсөнийг илэрхийлнэ. (1≤i≤n, 1≤x≤107)
Гаралтын формат
q+1 мөр хэвлэнэ. Эхний мөрөнд Тэмүүжин цэцэрлэгт хүрээлэнд анх очих үеийн, дараагийн мөрүүдэд очилт бүрийн дараах шаталсан палиндромын хамгийн их уртыг хэвлэнэ.
Хязгаарлалт
- 1≤n,q≤105
- 1≤ai,x≤107
- 1≤i≤n
Жишээ
5 3 4 3 2 1 3 3 5 4 4 5 3
3 1 3 5