تصطف أبقار Farmer John البالغ عددها $N$ ($1 \le N \le 50,000$) دائمًا بالترتيب نفسه عند الحلب اليومي. في أحد الأيام يقرر Farmer John تنظيم لعبة ألتيميت فريسبي مع بعض الأبقار. للتبسيط، سيختار مقطعًا متصلًا من الأبقار في طابور الحلب لتشارك في اللعبة. لكن لكي تستمتع جميع الأبقار، يجب ألا تختلف أطوالها كثيرًا.

أعدّ Farmer John قائمة تضم $Q$ ($1 \le Q \le 200,000$) مجموعة محتملة من الأبقار وأطوالها ($1 \le height \le 1,000,000$). لكل مجموعة، ساعده على تحديد الفرق في الطول بين أطول بقرة وأقصر بقرة فيها.

الإدخال

اقرأ المدخلات من الإدخال القياسي.

السطر 1: عددان صحيحان $N$ و$Q$ يفصل بينهما فراغ.

الأسطر $2 \ldots N+1$: يحتوي السطر $i+1$ على عدد صحيح واحد يمثل طول البقرة $i$.

الأسطر $N+2 \ldots N+Q+1$: عددان صحيحان $A$ و$B$ ($1 \le A \le B \le N$) يمثلان نطاق الأبقار من $A$ إلى $B$ شاملًا الطرفين.

الإخراج

اكتب المخرجات إلى الإخراج القياسي.

الأسطر $1 \ldots Q$: يحتوي كل سطر على عدد صحيح واحد يجيب عن الاستعلام المقابل ويشير إلى الفرق في الطول بين أطول بقرة وأقصر بقرة في النطاق.

أمثلة

الإدخال 1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

الإخراج 1

6
3
0

مصدر المسألة: USACO، يناير 2007، Gold