301D орчуулах · Codeforces.mn

# Ярослав ба хуваагчид
Ярославд $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

Гаралт

Оролт

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

Гаралт