Fişierul intrare/ieşire:pq.in, pq.outSursăACM ICPC - Romanian Programming Contest 2016
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pq

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 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.

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.

Restricţii

  • 1 ≤ N, Q ≤ 100000
  • 0 ≤ A(i) ≤ 99999
  • 1 ≤ L ≤ R ≤ N

Exemplu

pq.inpq.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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?