D. Ярослав ба хуваагчид

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

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

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

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

Ярославд $n$ ширхэг давхцаагүй бүхэл тоонуудаас бүрдсэн $p = p_{1}, p_{2}, ..., p_{n}$ $(1 ≤ p_{i} ≤ n)$ гэсэн массив байгаа. Тэр $m$ ширхэг хүсэлтэнд хариулах болсон:

  • $i$-р хүсэлт нь хос бүхэл $l_{i}$, $r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ тоонуудаар илэрхийлэгдэнэ.
  • $l_{i}, r_{i}$ хүсэлтийн хариулт нь $q$, $w$ $(l_{i} ≤ q, w ≤ r_{i})$ хос бүхэл тоо байх ба $p_{q}$ нь $p_{w}$-гийн хуваагч байна.

Ярославд хүсэлтүүдэд хариулахад нь туслаарай.

Оролт

Эхний мөрөнд бүхэл $n$, $m$ $(1 ≤ n, m ≤ 2*10^{5})$ тоонууд агуулагдана. Хоёр дахь мөрөнд $n$ ширхэг давхцаагүй бүхэл $p_{1}, p_{2}, ..., p_{n}$ $(1 ≤ p_{i} ≤ n)$ тоонууд агуулагдана. Дараагийн $m$ ширхэг мөрөнд хүсэлтүүд байх буюу $i$-р мөрөнд бүхэл $l_{i}, r_{i}$ $(1 ≤ l_{i} ≤ r_{i} ≤ n)$ тоонууд агуулагдана.

Гаралт

$m$ ширхэг бүхэл тоо хэвлэнэ. Хүсэлтийн хариултуудыг харгалзуулан хэвлэнэ.

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

Орчуулсан: Даариймаа

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

Оролт
1 1
1
1 1
Гаралт
1
Оролт
10 9
1 2 3 4 5 6 7 8 9 10
1 10
2 9
3 8
4 7
5 6
2 2
9 10
5 10
4 10
Гаралт
27
14
8
4
2
1
2
7
9
Сэтгэгдлүүдийг ачааллаж байна...