მოცემულია 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: თითოეული სტრიქონი უნდა შეიცავდეს ერთ მთელ რიცხვს - შესაბამისი ინტერვალის უდიდესი და უმცირესი ელემენტების სხვაობას.