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

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

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

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

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

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


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

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

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

შემდეგი Q ხაზი შეიცავს ორ ცალს მთელ A და B (0AB1,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 დაკოპირება