לחליבה היומית, $N$ הפרות של Farmer John ($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