Codeforces Round #804 (Div. 2)
3 өдрийн дараа |
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