Rezolvare PBinfo #1394

Enunț

Într-o zi, Gigel a găsit pe masa tatălui său o foaie A4 pe care era trecut șirul denumit “devt” sub forma 1, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, ... , n. Dedesubtul acestui șir găsește un text alcătuit din k întrebări de forma a, b cu semnificația “Câte numere din acest șir se află în intervalul [a,b]?”.

Cerința

Ajutați-l pe Gigel să răspundă corect la toate cele k întrebări.

Date de intrare

Fișierul de intrare devt.in conține pe prima linie numerele naturale n și k, iar pe următoarele k linii numerele a, b cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire devt.out va conține k linii, pe fiecare linie i aflându-se un număr natural, reprezentând răspunsul întrebării i.

Restricții și precizări

• 0 ≤ a ≤ b ≤ n ≤ 100.000
• 1 ≤ k ≤ 5000
• n aparține șirului devt

Exemplu:

devt.in

25 5
3 7
12 20
3 4
16 24
12 24

devt.out

2
6
1
6
9

Explicație

În intervalul [3,7] se află 2 numere din șir.
În intervalul [12,20] se află 6 numere din șir.
În intervalul [3,4] se află 1 număr din șir.
În intervalul [16,24] se află 6 numere din șir.
În intervalul [12,24] se află 9 numere din șir.