وصلت للتو $n$ طرود، مرقمة من $1$ إلى $n$، إلى أحد المستودعات. جاءت بالترتيب $a_1, \dots, a_n$، ونريد ترتيبها بحيث تصبح بالترتيب $1, 2, \dots, n$.

تعمل آلة الفرز في المستودع على مراحل. تقبل كل مرحلة صفاً $a_1, \dots, a_n$ من الطرود وتعمل كما يلي: أولاً، يوضع الطرد الأول $a_1$ في صف جديد. بعد ذلك، لكل طرد $a_i$ حيث $i = 2, \dots, n$، إذا كان $a_i$ أكبر من الطرد الأخير (الأقصى يميناً) في الصف الجديد، تضع الآلة الطرد في نهاية الصف. وإلا، تضعه في مقدمة الصف.

إذا لم يكن الصف الجديد مرتباً، فإنه يُستخدم كمدخل للمرحلة التالية من آلة الفرز.

اكتب برنامجاً يساعد في اختبار ما إذا كانت الآلة تعمل كما هو مقصود من خلال الإجابة عن استعلامات على الشكل "أي طرد يقع في الموضع $b$ بعد $t$ مراحل".

الإدخال

يحتوي السطر الأول من الإدخال على عددين صحيحين $n$ و $q$ ($1 \le n, q \le 5 \cdot 10^5$)، يمثلان عدد الطرود وعدد الاستعلامات على التوالي.

يحتوي السطر الثاني على متتالية من $n$ أعداد صحيحة $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, $a_i \ne a_j$) تمثل الترتيب الابتدائي للطرود.

تحتوي الأسطر الـ $q$ التالية على الاستعلامات؛ يحتوي السطر $i$ على عددين صحيحين $t_i$ و $b_i$ ($0 \le t_i \le 10^9$, $1 \le b_i \le n$)، يمثلان الاستعلام رقم $i$.

الإخراج

اطبع $q$ أسطر بالضبط. يجب أن يحتوي السطر $i$ على الإجابة عن الاستعلام رقم $i$.

إذا نفذت الآلة أقل من $t_i$ مراحل، فاكتب $-1$. وإلا، فاكتب رقم الطرد الموجود في الموضع $b_i$ من اليسار بعد تنفيذ $t_i$ مراحل.

أمثلة

الإدخال 1

5 4
2 1 3 5 4
1 1
3 2
4 1
0 4

الإخراج 1

4
2
-1
5

ملاحظة 1

ستنفذ الآلة ثلاث مراحل:

$$2\ 1\ 3\ 5\ 4 \to 4\ 1\ 2\ 3\ 5 \to 3\ 2\ 1\ 4\ 5 \to 1\ 2\ 3\ 4\ 5$$

الإدخال 2

1 1
1
1 1

الإخراج 2

-1