== include(page="template/taskheader" task_id="pq") ==

Poveste şi cerinţă...

Se da un sir de **N** numere naturale, **A[1], …, A[N]**. In acest sir definim o pereche de indici **(u,v)** ca fiind speciala daca sunt indeplinite toate cele 3 conditii de mai jos:
u < v
A[u] = A[v]
Nu exista niciun indice w (u<w<v) astfel incat A[u]=A[v]=A[w].
 
Costul unei perechi speciale (u,v) este egal cu v-u.
 
Se dau in plus Q interogari de tipul: dandu-se L si R, determinati costul maxim al unei perechi speciale incluse complet in intervalul [L,R] (adica avand L<=u <v<=R).
 
Date de intrare
	Pe prima linie a fişierului pq.in se află numerele naturale N si Q. Pe linia urmatoare se afla numerele naturale A[1], …, A[N], in ordine. Urmatoarele Q linii contin cate doua numere naturale, L si R, reprezentand o interogare.
 
Date de ieşire
	Fişierul pq.out trebuie să conţina Q linii, cate una pentru fiecare interogare: costul maxim al unei perechi speciale incluse complet in intervalul [L,R]. Daca nu exista nicio astfel de pereche speciala, afisati -1.

h2. Date de intrare