თივის ზვინების დათვლა

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2016/17, DEC, SILVER

ფერმერმა ჯონმა განალაგა თავისი N თივის ზვინი (1≤N≤100,000) ერთი წრფის გასწვრივ რაღაც პოზიციებზე. რათა დარწმუნდეს რომ თივის ზვინები კარგად არის განაწილებული, ის გთხოვთ უპასუხოთ მის Q (1≤Q≤100,000) ცალ შეკითხვას, თითოეულ შეკითხვაზე გვაინტერესებს თივების ზვინების რაოდენობა კონკრეტულ ინტერვალზე.

შემავალი მონაცემების ფორმატი:

პირველი ხაზი შეიცავს N და Q - ს. შემდეგი N ხაზი შეიცავს განსხვავებულ მთელ რიცხვებს თითოეული 0…1,000,000,000-მდე, განსაზღვრავს რომ ამ პოზიციაზე გვაქვს 1 თივის ზვინი.

შემდეგი Q ხაზი შეიცავს ორ ცალს მთელ A და B (0≤A≤B≤1,000,000,000) რიცხვებს, რომლებიც განსაზღვრავენ შეკითხვას თუ რამდენი თივის ზვინია A პოზიციიდან B პოზიციის ჩათვლით.

გამოტანის ფორმატი:

გამოსატანი ფაილი უნდა შეიცავდეს Q ცალ ხაზს. ყოველი შეკითხვისთვის გამოიტანეთ თივის ზვინების რაოდენობა კონკრეტულ ინტერვალში.

 

 



მაგალითები

შესატანი მონაცემები
4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10
                  დაკოპირება
გამოსატანი მონაცემები
2
2
3
4
1
0
                  დაკოპირება