وضع 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