| Fişierul intrare/ieşire: | pq.in, pq.out | Sursă | ACM ICPC - Romanian Programming Contest 2016 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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.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 |
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.
