Farmer John סידר זה עתה את $N$ חבילות החציר שלו ($1 \leq N \leq 100,000$) בנקודות שונות לאורך הדרך החד־ממדית החוצה את החווה שלו. כדי לוודא שהן מרווחות כראוי, עזרו לו לענות על $Q$ שאילתות ($1 \leq Q \leq 100,000$), שכל אחת מהן שואלת על מספר חבילות החציר בקטע מסוים לאורך הדרך.

קלט

השורה הראשונה מכילה את $N$ ואת $Q$.

השורה הבאה מכילה $N$ מספרים שלמים שונים, כל אחד בטווח $0 \ldots 1,000,000,000$, המציינים שבכל אחת מהנקודות האלה נמצאת חבילת חציר.

כל אחת מ־$Q$ השורות הבאות מכילה שני מספרים שלמים $A$ ו־$B$ ($0 \leq A \leq B \leq 1,000,000,000$), המגדירים שאילתה על מספר חבילות החציר בין $A$ ל־$B$, כולל הקצוות.

פלט

יש לכתוב $Q$ שורות פלט. לכל שאילתה, הדפיסו את מספר חבילות החציר בקטע המתאים לה.

דוגמאות

קלט 1

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

פלט 1

2
2
3
4
1
0

מחבר הבעיה: Nick Wu