D. Найзууд ба дэд дарааллууд

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

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

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

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

Майк болон !Майк нар хуучны бага насны өрсөлдөгчид ба програмчлахаас бусад бүх зүйл дээр тэдний хийдэг зүйлс эсрэг. Өнөөдөр тэд өөрсдийн шийдэж чадахгүй асуудалтай тулгарсан ч магадгүй тантай хамт шийдэж чадах ч юм билүү?

Энэ хоёрт тус бүр нь $n$ урттай бүхэл тоон $a$ ба $b$ дараалал байна. Өгөгдсөн хоёр бүхэл тоо бүхий $(l, r)$ асуулгаас Майк нэн даруй утгыг хэлж чадах бол !Майк нэн даруй утгыг хэлж чадна.

Одоо робот (та!) тэднээс $(l, r)$ $(1 ≤ l ≤ r ≤ n)$ хос бүхэл тоонуудын бүх боломжит ялгаатай асуулгуудыг (тэр яг $n(n + 1) / 2$ асуулга асууна) асуух ба тэдгээрийн хариулт хэдэн удаа таарч байгааг тоолох ба хэдэн хосын хувьд биелэж байгааг тоолно.

Робот хэдэн тохиолдол тоолох вэ?

Оролт

Эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 200 000$) байна.

Хоёр дахь мөрөнд $n$ бүхэл тоон утга $a_{1}, a_{2}, ..., a_{n}$ ($ - 10^{9} ≤ a_{i} ≤ 10^{9}$) байх буюу $a$ дараалал юм.

Гурав дахь мөрөнд $n$ бүхэл тоон утга $b_{1}, b_{2}, ..., b_{n}$ ($ - 10^{9} ≤ b_{i} ≤ 10^{9}$) байх буюу $b$ дараалал юм.

Гаралт

Роботын тоолох нөхцөлийг хангах хосуудын тоог илэрхийлэх нэг бүхэл тоог хэвлэ.

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

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

Оролт
6
1 2 3 2 1 4
6 7 1 2 3 2
Гаралт
2
Оролт
3
3 3 3
1 1 1
Гаралт
0

Тэмдэглэл

Эхний жишээн дээрх тохиолдлууд нь:

1.$max{2} = min{2}$ учраас $l = 4$,$r = 4$.

2.$max{2, 1} = min{2, 3}$ учраас $l = 4$,$r = 5$.

Хоёр дахь жишээн дээр Майк ямар ч асуулгад $3$ гэж хариулах бол !Майк ямар ч асуулгад $1$ гэж хариулах учраас нөхцөлийг хангах тохиолдол байхгүй.

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