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&leq; u < v &leq; 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

Pe prima linie a fisierului de intrare $pq.in$ se afla 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.

Fişierul de intrare $pq.in$ ...

h2. Date de ieşire

Fisierul de iesire $pq.out$ trebuie sa contina **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**.

În fişierul de ieşire $pq.out$ ...

h2. Restricţii

* $1 ≤ N, Q ≤ 100000$
* $0 ≤ A(i) ≤ 99999$
* $1 &le; L < R &le; N$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. pq.in |_. pq.out |

|8 6
1 7 1 3 1 7 3 3
1 2
1 3
1 5
2 8
4 8
7 8
|-1
2
2
4
3
1|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

In intervalul **[1,2]** nu exista nicio perche speciala. In intervalul **[1,3]** perechea speciala **(1,3)** are costul maxim. In intervalul **[1,5]** perechile speciale **(1,3)** si **(3,5)** au costul maxim. In intervalul **[2,8]** perechea speciala **(2,6)** are costul maxim. In intervalul **[4,8]** perechea speciala **(4,7)** are costul maxim. In intervalul **[7,8]** perechea speciala **(7,8)** are costul maxim.

...

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