108C: ზუსტად ორჯერ

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

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

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

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


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

ყველა შეკითხვა შედგება 2 მთელი რიცხვისგან, რომლებიც აღნიშნავენ მასივის რომელიმე ინტერვალის მარცხენა და მარჯვენა ბოლოებს. თითო შეკითხვაზე პასუხი არის ისეთი განსხვავებული რიცხვების რაოდენობა, რომლებიც ზუსტად ორჯერ გვხვდებიან ამ ინტერვალში.

 შემომავალი მონაცემები: პირველ ხაზზე შემოდის ორი მთელი რიცხვი N და Q (1 ≤ N, Q ≤ 500 000). მეორე ხაზზე შემოდის N ცალი ნატურალური რიცხვისგან შედგენილი მასივი, რომლის თითოეული ელემენტი ნაკლებია 1 000 000 000-ზე. შემდეგ Q-ცალ ხაზზე შემოდის შეკითხვები, რომლებიც შედგება L და R მთელი რიცხვებისგან (1 ≤ L ≤ R ≤ N).

გამომავალი მონაცემები: თითოეული შეკითხვისთვის უნდა დაბეჭდოთ პასუხი შესაბამისი მიდევრობით.


მაგალითები

შესატანი მონაცემები

vaxtangiC4exCC44 C4

გამოსატანი მონაცემები

vaxtangiex

შესატანი მონაცემები

12ab112ab2ab 12ab

გამოსატანი მონაცემები

EMPTY