该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

当你进入ACM实验室的那天，一切都将作废。你的本科作废，你的专业作废，星星作废，月亮作废，银河系作废，宇宙作废，你的爱作废，你的恨作废，你的前半生作废，你的现女友作废。悬梁五战终进实验室，大雪深埋垃圾本科！实验室的录取通知书会像一场大雪一样深埋所有不堪过往，冲！

题目描述

Rahn 是埃湖大学的一名大一新生，梦想着加入学校的ACM实验室。这天他前往ACM实验室参加新生选拔赛，但是天空却飘起了大雪，通向实验室的路被大雪深埋了。

通向实验室的路可以抽象成一维的 $N$ 格，其中第 $i$ 格被深 $f_i$ 的雪覆盖。Rahn 当前在第 $1$ 格，他需要前往实验室所在的第 $N$ 格。

好在 Rahn 是一个预案充足的选手，他准备了 $M$ 双靴子，其中第 $i$ 双靴子能够一次前进至多 $d_i$ 格，且能够使他站立在雪深至多 $s_i$ 的格子上。

现在 Rahn 想知道，哪些靴子能帮他顺利通过这段路程。

输入

输入第一行包含两个整数 $N,M(1\le N,M\le 10^5)$，表示路程的长度（格数）以及 Rahn 准备的靴子数量。

第二行包含 $N$ 个空格隔开的整数 $f_1,\dots,f_N$，$f_i$ 表示第 $i$ 格被覆盖的雪深。保证 $1\le f_i\le 10^9, f_1=f_N=0$。

接下来 $M$ 行，每行两个整数 $s_i,d_i(0\le s_i\le 10^9, 1\le d_i\le N-1)$ 表示 Rahn 第 $i$ 双靴子的属性（具体见描述）。

输出

输出 $M$ 行，对于第 $i$ 行，若小 M 的第 $i$ 双靴子可以通过这段路程，则输出 $1$，否则输出 $0$。

样例

8 7
0 3 8 5 6 9 0 0
0 5
0 6
6 2
8 1
10 1
5 3
150 7

0
1
1
0
1
1
1