Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2019-07-13 10:18:50.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:verkhoyansk.in, verkhoyansk.outSursăTuymaada 2019
AutorAlexandru PetrescuAdăugată dealexpetrescuAlexandru Petrescu •alexpetrescu
Timp execuţie pe test1.25 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Verkhoyansk

Marcel has planned a trip in the Verkhoyansk Range, a 1200 km mountain range in the Sakha Republic. The landscape can be seen as an array of N integers with values between 1 and N, representing the heights of the mountain peaks along the range.

Marcel has Q friends. Friend i will visit all peaks with indices from L[i] to R[i]. Marcel wants to know, for each of them, what is the smallest positive integer height of a peak each friend will not visit. He needs to know this in order to optimally plan his next trip.

For example, if one friend visits peaks with heights 3 2 5 1 1 6 3 5, the smallest positive integer height of a peak he didn't visit is 4.

Input

The first line of the input file verkhoyansk.in contains numbers N and Q. The second line contains N integers with values between 1 and N, representing the heights of mountain peaks. The following Q lines contain 2 numbers, L[i] and R[i], with 0 ≤ L[i] ≤ R[i] ≤ N - 1.

Output

In the output file verkhoyansk.out there will be Q lines. Line i contains the smallest positive integer height of a peak friend number i will not visit.

Constraints

  • 1 ≤ N ≤ 300.000, 1 ≤ Q ≤ 600.000
  • For 8 points, N ≤ 1.000, Q ≤ 10.000
  • For other 8 points, N ≤ 100.000, Q ≤ 200.000 and all the heights are at most 50
  • For other 56 points, N ≤ 100.000, Q ≤ 200.000
  • Note that the scoring is not the same as the one in the official onsite contest
  • Note that the array of heights is "0-indexed"

Exemplu

verkhoyansk.inverkhoyansk.out
14 16
3 4 3 2 5 1 6 7 2 1 6 2 4 3
0 4
0 5
9 13
9 12
3 12
2 12
2 11
1 11
3 13
5 13
8 13
0 7
0 8
6 8
6 9
6 10
1
6
5
3
3
8
4
8
8
5
5
8
8
1
3
3
16 32
8 7 6 5 2 1 8 7 1 2 3 4 5 6 3 4
1 14
0 2
2 5
1 13
12 14
1 9
5 14
1 15
5 10
2 2
4 10
5 11
5 13
0 10
0 15
1 13
7 15
3 6
12 14
3 5
14 14
2 10
0 12
2 15
0 0
4 8
0 12
0 7
6 15
3 5
1 14
2 14
9
1
3
9
1
3
9
9
4
1
4
5
9
4
9
9
8
3
1
3
1
4
9
9
1
3
9
3
9
3
9
9

Tutorial

You can see a solution description in problem's editorial

Request

Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?