D. Биеийн тамирын хүмүүжил

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

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

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

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

Вася сургуулийн биеийн тамирын багш. Бусад биеийн тамирын багш нараас ялгаатай нь Вася сурагчид өндөр намаараа зогссон байхад дургүй. Үүний оронд хүүхдүүдийг өндрөөр нь $a_1$, $a_2$, $...$, $a_n$ дарааллаар зогссон нь дээр гэж үздэг, энд $a_i$ нь эгнээний $i$-р хүүхдийн өндөр. Хүүхдүүд энэхүү өвөрмөц дарааллыг санахад хэцүү байсан бөгөөд өнөөдөр тэд дараах байдлаар: $b_1$, $b_2$, $...$, $b_n$ гэж жагссан байсанд Вася үнэхээр их бухимдав. Одоо Вася ахин байрыг нь сольж $a_1$, $a_2$, $...$, $a_n$ дараалалд оруулахыг хүслээ. Вася үйлдэл бүрт жагсаалаас зэрэгцэн зогсож байгаа хоёр хүүхдийг сонгон байрыг нь солино. Васягийн хүссэн байрлалд оруулахад нь Васяд тусална уу. Заавал хамгийн цөөн үйлдлээр гүйцэтгэх шаардлагагүй.

Оролт

Эхний мөрөнд сурагчдын тоо болох $n$ ($1 ≤ n ≤ 300$) бүхэл тоог агуулна. Хоёрдахь мөр сурагчдын байрлах ёстой дараалал болох $n$ ширхэг зайгаар тусгаарлагдсан $a_i$ ($1 ≤ a_i ≤ 10^9$) тоог агуулна, энд $a_i$ нь $i$-р байрлалд зогсох хүүхдийн өндөр. Гурав дахь мөр хүүхдүүдийн одоогийн байрлалыг илэрхийлэх $n$ ширхэг зайгаар тусгаарлагдсан $b_i$ ($1 ≤ b_i ≤ 10^9$) тоонуудыг агуулна, энд $b_i$ нь $i$-р байрлалд зогсож байгаа хүүхдийн өндөр. Зарим хүүхдүүд ижил өндөртэй байж болно. Одоо зогсож байгаа болон шаардлагатай байрлалд зогсох өндрүүд ямар ч байсан давхцна, өөрөөр хэлбэл $a$, $b$ олонлог нь тэнцүү байна.

Гаралт

Эхний мөрөнд үйлдлийн тоо болох $k$ ($0 ≤ k ≤ 10^6$) бүхэл тоог хэвлэ. Энэ нь хамгийн цөөн байх албагүй боловч $10^6$-аас хэтрэхгүй байх ёстой. Дараагийн $k$ мөрөнд, мөр бүрт зайгаар тусгаарлагдсан хоёр бүхэл тоо өгөгднө. Мөрөн дэх $p_i$, $p_i + 1$ ($1 ≤ p_i ≤ n - 1$) тоо нь Вася $p_i$, $p_i + 1$ байрлал дахь хүүхдүүдийн байрыг солино гэсэн үг.

Орчуулсан: Sugardorj

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

Оролт
4
1 2 3 2
3 2 1 2
Гаралт
4
2 3
1 2
3 4
2 3
Оролт
2
1 100500
1 100500
Гаралт
0
Сэтгэгдлүүдийг ачааллаж байна...