Танд $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" гэж хэвлэнэ.