E. Берландын байршлын систем

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

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

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

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

Берландад автобус нийслэлийн төв гудамжаар явдаг. Энэхүү гудамж нь төв талбайгаас эхлээд маш урт хэсгийг туулдаг. $n$ автобусны зогсоол гудамж дагуу байрладаг, тэдгээрийн $i$ дэхь нь төв талбайгаас $a_{i}$ зайд оршдог, бүх зай хоорондоо ялгаатай, автобусны зогсоолууд ихсэх дарааллаар дугаарлагдсан буюу $i$-н хувьд $a_{i} < a_{i + 1}$ томьёотой 1-с $n - 1$ хүртэл дугаарласан. Автобус эхний зогсоолоос аяллаа эхэлж $2$, $3$ зогсоолуудыг өнгөрөөж цааш явдаг. Зогсоол $n$ дээр хүрээд зогсоол $1$-рүү эсрэг чиглэлд эргэн яваад эсрэг дарааллаар дундах зогсоолуудыг өнгөрөн явдаг. Үүний дараа дахин $n$ зогсоолын зүгт хөдөлгөөнөө эхлүүлдэг. Бүхэл өдрийн турш энэ автобус энэ маршрутаар завсарлагагүй явдаг.

Энэхүү автобус Берланд байршлын системээр тоноглогдсон. Автобус зогсоолоор дамжин өнгөрөхөд систем түүний дугаарыг тэмдэглэн хадгалдаг.

Системийн гол онцлогуудын нэг бол ямар ч 2 зогсоолын хоорондох зайн талаар асуухад хариу өгдөг. Системийн гол модуль нь замын зогсоолуудын талаар өгөгдлийг шаардах бөгөөд зогсоолын дугаарыг автобусны өнгөрсөнд хэр их явсан дээр үндэслэн гаргадаг. Энэ модуль аялсан замын уртыг гарган харуулна (хэрэв замын уртыг тогтоох боломжгүй бол -1). Энэ модуллын үйлдэл нь зогсоолын дугааруудыг автобус явж өнгөрсөн дарааллаар бус, ихсэх дарааллаар харуулдаг төвөгтэй талтай.

Жишээлбэл, хэрэв $6$-н ширхэг автобусны буудалтай, автобус зогсоолын дугаар $5$-аас эхэлж зогсоолын дугаар $3$ дээр зогсох ёстой бол автобус дараах байдлаар зогсоолуудыг өнгөрнө : , харин энэ зайн талаарх байршлын системээс мэдээлэл авах гэвэл дараах хэлбэрээр ирнэ: $3, 4, 5, 5, 6$. Хэрэв зогсоол $5$-аас зогсоол $3$ хүртэлх зам дээр автобус $1$-дүгээр зогсоолыг өнгөрөх ёстой (өөрөөр хэлбэл, хэрэв бид зогсоол $5$-аас замдаа гараад зогсоол $3$ дээр 2 удаагаа зогсох хүртэл замыг авч үзвэл) бол хүсэлт дараах хэлбэрээр ирнэ : $1, 2, 2, 3, 3, 4, 5, 5, 6$.

Та Берланд программчдын амжилт болон энэ үйлдлийн кодыг дахин хийх хэрэгтэй.

Оролт

Эхний мөрөнд нийт буудлын тоо болох нэг бүхэл тоо ($2 ≤ n ≤ 2*10^{5}$) өгөгдөнө.

2 дахь мөрөнд $n$ ширхэг бүхэл тоонууд a_{i} ($1 ≤ a_{i} ≤ 10^{9}$) өгөгдөнө. Энэ нь төв талбайгаас $i$ дэхь буудал хүртэлх зай болно. 2 дахь мөрөн дахь тоонууд ихсэх дарааллаар өгөгдөнө.

3 дахь мөрөнд автобусны байршлын системийн хариулах нийт буудлын тоо болох нэг бүхэл тоо $m$ ($1 ≤ m ≤ 4*10^{5}$) өгөгдөнө.

4 дахь мөрөнд ихсэх дараалалтай байршлын системийн хариу болох $m$ ширхэг бүхэл тоонууд b_{i} ($1 ≤ b_{i} ≤ n$) өгөгдөнө. Буудлын дугаар нь автобус энэ буудал дээр хэдэн удаа зогссон яг адилхан удаагаар оролтонд өгөгдөнө.

Оролтонд тохирох зам олдох нь баталгаатай.

Гаралт

Ганц мөрөнд заасан зогсоолуудаар явахад автобусны явах замын уртыг хэвлэнэ үү. Хэрвээ энэ замын уртыг олох боломжгүй бол $-1$ гэж хэвлэнэ үү.

Орчуулсан: Энхлут

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

Оролт
6
2 3 5 7 11 13
5
3 4 5 5 6
Гаралт
10
Оролт
6
2 3 5 7 11 13
9
1 2 2 3 3 4 5 5 6
Гаралт
16
Оролт
3
10 200 300
4
1 2 2 3
Гаралт
-1
Оролт
3
1 2 3
4
1 2 2 3
Гаралт
3

Тэмдэглэл

Эхний тест нь бодлогоны эхний жишээ болно.

2 дахь тест нь бодлогоны 2 дахь жишээ болно.

3 дахь тестэнд ялгаатай замын урттай 2 боломжит зам байна. Бидний олох гэж буй замыг тодорхой зааж өгөөгүй учир хэвлэх боломжгүй.

4 дахь тестэнд асуултын хариултанд 2 ялгаатай зам байгаа ч адилхан урттай. Иймээс бидний хариултыг хэвлэх боломжтой.

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