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

قائمة $Q$ ($1 \le Q \le 200,000$) مجموعات محتملة وأطوال ($1 \le height \le 1,000,000$): أوجد فرق الأطول والأقصر لكل مجموعة.

الإدخال

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

السطر 1: الصحيحان $N$ و$Q$ بمسافة.

الأسطر $2..N+1$: السطر $i+1$ بطول البقرة $i$ الصحيح.

الأسطر $N+2$..$N+Q+1$: الصحيحان $A$ و$B$ ($1 \le A \le B \le N$)، المجال من $A$ إلى $B$ شاملًا.

الإخراج

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

الأسطر $1..Q$: صحيح لكل جواب، فرق الأطول والأقصر بالمجال.

أمثلة

الإدخال 1

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

الإخراج 1

6
3
0

المصدر: USACO يناير 2007، الفضي