Nosaukums
Kāpšana un krišana (kapsana_krisana)
Laika limits
2.00s
Atmiņas limits
32.0 MB
Grūtība
55%

Definīcija

Sacensībās RatingCode piedalās n lietotāji, kur k-tajam lietotājam piešķirts reitings ar vērtību ak. Vienā sacensību reizē katra lietotāja reitings var vai nu palielināties, vai nu samazināties par veselu pozitīvu skaitli d. Lietotājiem interesē jautājumi veidā: kāds ir mazākais nepieciešamais sacensību reižu skaits, lai no sākotnējā stāvokļa i-tajam lietotājam reitings kļūtu j-tais lielākais un nebūtu vienāds ar neviena cita lietotāja reitingu? Ievērojiet, ka reitings var kļūt arī negatīvs skaitlis.


Ievaddatu raksturojums

Pirmajā rindā doti divi veseli pozitīvi skaitļi n un d, lietotāju skaits un reitinga izmaiņas vērtība vienā sacensību reizē (1 n 106, 1 d 109).
Otrajā rindā doti n veseli pozitīvi skaitļi a1, a2, ..., an, lietotāju reitingu vērtības (109 a_1 > a_2 > ... > a_n 1).
Trešajā rindā dots viens skaitlis q, jautājumu skaits (1 q 106).
Katrā no nākošajām q rindām dots pa diviem skaitļiem i un j, lietotāja sākotnējā vieta, un prasītā vieta (1 ≤ i, j ≤ n, i ≠ j).


Izvaddatu raksturojums

Jāizvada rinda no q skaitļiem, atdalītiem ar tukšumzīmēm, kas ir atbildes uz jautājumiem tādā secībā, kādā tie uzdoti ievadā.


Piezīmes

Punkti par testiem:

  1. 20% - a1 100.
  2. 30% - a1 5000.
  3. 50% - uzdevumā dotie ierobežojumi.

Autors: Jevgēnijs Vihrovs.


Paraugdati

Stdin
5 10
50 41 35 23 10
5
1 5
5 1
3 4
5 3
4 2
Stdout
3 3 1 2 1

Stdin
10 100
3407 3067 2959 2873 2864 2849 2793 2790 2783 2780
4
10 1
2 7
5 3
1 6
Stdout
4 2 1 3

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.