B. Үр ашигтай арга

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

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

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

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

Нэг удаа багийн сургалтын үеэр Вася, Петя, Саша нар массив дахь шугаман хайлтыг хэрэгжүүлж байх үедээ асуудалтай тулгарсан.

Хөвгүүдийнхээр бол шугаман хайлт дараах байдлаар ажилладаг. Үүнд тодорхойлогдчихсон байгаа массивийн элементүүдийг ээлж ээлжээр нь таны олох гэж буй тоотой харьцуулна. Таны хайж буй тоотой тэнцүү элемент олдвол хайлт дуусна. Алгоритмын үр ашигтай байдал нь гүйцэтгэсэн үйлдлийн тоо байна. Шугаман хайлт цөөхөн харьцуулалт хийсэн бол үр ашиг их байна.

Вася хэрвээ шугаман хайлт нь $1$-р элементээс эхлээд (энэ бодлогонд бид массивийн элементүүдийг $1$-c $n$ хүртэл дугаарлагдсан гэж үзнэ) $n$-р элемент дээр дуусах элементүүдээр дарааллан давтан ажиллавал илүү үр ашигтай байна гэдэгт итгэж байна. Харин Петя Васягийн буруу хэрвээ хайлт $n$-р элементээс эхлээд $1$-р элемент дээр дуусах элементүүдээр дарааллан давтан ажиллавал илүү үр ашигтай гэв. Саша харин энэ хоёр арга бол яг адилхан гэж хэлэв.

Эцэст нь ажлаа эхлэхийн тулд тэд маргааныг зохицуулахаар шийдсэн ба хоёр аргыг жишээн дээр харьцуулахаар болсон. Үүний тулд тэд $1$-c $n$ хүртэлх бүхэл тоонуудын сэлгэмэл бүхий массив авсан ба дараах хэлбэртэй $m$ асуулга бэлдсэн: массив дахь $b_{i}$ утгатай элементийг ол. Тэд хоёр аргын аль алинд нь нийт асуулгуудад хариулахад шаардлагатай нийт харьцуулалтын тоог мэдэхийг хүсч байна. Хэрвээ эхний хайлт цөөн харьцуулалт хийж байвал ялагч нь Вася байна. Хэрвээ хоёр дахь хайлт цөөн харьцуулалт хийж байвал ялагч нь Петя байна. Харин хоёр арга ижил тооны харьцуулалт хийж байвал Саша ялагч болно.

Гэхдээ энд нэг асуудал байгаа нь шугаман хайлт маш удаан. Энэ нь хөвгүүд яагаад сургалтын төгсгөлд таныг ирэхээс өмнө хэнийх нь зөв гэдгийг шийдэхгүй байх шалтгаан юм. Тэдэнд маргаанд хэн ялахыг нь тодорхойлж өгнө үү.

Оролт

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

Гурав дахь мөрөнд бүхэл тоо $m$ $(1 ≤ m ≤ 10^{5})$ байх ба асуулгуудын тоо юм. Сүүлийн мөрөнд зайгаар тусгаарландсан $m$ бүхэл тоо $b_{1}, b_{2}, ..., b_{m}$ $(1 ≤ b_{i} ≤ n)$ байх ба хайлтын асуулгууд юм. Асуулгууд давхцаж болно.

Гаралт

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

C++ хэлэнд 64 битийн бүхэл тонуудыг унших болон бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. $cin$, $cout$ урсгалууд болон $\%I64d$ тодорхойлогчийг ашиглаарай.

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

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

Оролт
2
1 2
1
1
Гаралт
1 2
Оролт
2
2 1
1
1
Гаралт
2 1
Оролт
3
3 1 2
3
1 2 3
Гаралт
6 6

Тэмдэглэл

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

Хоёр дахь жишээн дээр нөгөө талаас Васягийн арга хоёр харьцуулалт хийх (эхлээд $1$-р элементтэй тэгээд $2$-р элементтэй) бол Петягийн арга шаардлагатай утгыг олоход нэг харьцуулалт хийнэ (эхлээд $2$-р элементтэй харьцуулна).

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