D. Хамгийн ойрхон тэнцүү элементүүд

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

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

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

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

Танд $a_{1}, a_{2}, ..., a_{n}$ дараалал болон $l_{j}, r_{j}$ ($1 ≤ l_{j} ≤ r_{j} ≤ n$) байх $m$ ширхэг хүсэлтүүд өгөгдөнө. Хүсэлт бүрийн хувьд дараах нөхцлийг хангах бөгөөд хоорондох зай нь хамгийн бага байх $a_{x}$ ба $a_{y}$ ($x ≠ y$) хосын хоорондох зайг хэвлэнэ.

  • Хоёр элементийн дугаарууд [$l_{j}, r_{j}$] завсрын хооронд оршино. Өөрөөр хэлбэл $l_{j} ≤ x, y ≤ r_{j}$ байна;
  • Элементүүдийн утгууд хоорондоо тэнцүү буюу $a_{x} = a_{y}$ байна.

Хоорондох зай гэдэгт $|x - y|$ утгыг ойлгоно.

Оролт

Оролтын эхний мөрөнд $n$, $m$ ($1 ≤ n, m ≤ 5 \cdot 10^{5}$) бүхэл тоонууд байх ба эдгээр нь харгалзан дарааллын урт болон хүсэлтүүдийн тоог илэрхийлнэ.

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

Дараагийн $m$ ширхэг мөрөнд хүсэлтүүд байна. Мөр бүрт нэг хүсэлт байх ба $l_{j}, r_{j}$ ($1 ≤ l_{j} ≤ r_{j} ≤ n$) хос тоонуудаар өгөгдөнө.

Гаралт

Хүсэлт бүрийн хариу болох $m$ ширхэг бүхэл тоо хэвлэнэ. Зарим хүсэлтийн хувьд боломжит хариу байхгүй бол хүсэлтийн хариуг "-1" гэж хэвлэнэ.

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

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

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