დაბალანსებული მწკრივი

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

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

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

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

წყარო: USACO, 2007/08, JAN, SILVER


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

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

სტრიქონი 1: ორი მთელი რიცხვი, N და Q
სტრიქონები 2..N+1: შეიცავს თითო რიცხვს - შესაბამისი ნომრის მქონე მასივის ელემენტს. 
სტრიქონები N+2..N+Q+1: ორი მთელი რიცხვი A და B (1 ≤ A ≤ B ≤ N), რომლებიც აღწერენ ინტერვალს A-ს და B-ს ჩათვლით.
 
გამოსატანი მონაცემები:
 
სტრიქონები 1..Q: თითოეული სტრიქონი უნდა შეიცავდეს ერთ მთელ რიცხვს - შესაბამისი ინტერვალის უდიდესი და უმცირესი ელემენტების სხვაობას.

 

 

 




მაგალითები

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