{"raw_statement":[{"iden":"statement","content":"有一列数 $a_1,\\ldots,a_n$ 和 $q$ 次操作，每次操作形如「删掉长为 $d_i$ 的前缀或后缀，且需要保证这个前缀和后缀中所有元素都大于等于 $s_i$。」每次操作前，你可以选择长度任意的前缀或后缀（可以为空，且两端可同时选择），并删除它。如果某次操作无法进行，则停止这次和之后的所有操作。问最多可以进行多少次操作。"},{"iden":"input","content":"第一行两个正整数 $n,q\\ (1\\le n\\le 5\\ 000,1\\le q\\le 2\\cdot 10^5)$，表示序列长度和操作次数。\n\n第二行 $n$ 个正整数 $a_i\\ (1\\le a_i\\le 10^9)$，表示这个数列。\n\n接下来 $q$ 行，每行两个整数 $d_i,s_i\\ (1\\le d_i\\le n,1\\le s_i\\le 10^9)$，表示一次操作。"},{"iden":"output","content":"输出一行一个整数，表示最多能进行多少次操作。"},{"iden":"note","content":"样例 $3$ 解释：\n\n首先删除前缀 $(1)$，之后进行第一次操作，删除前缀 $(3,2,5)$。此时序列变为 $(1,4,6,2,1)$。\n\n然后删除前缀 $(1)$，之后进行第二次操作，删除前缀 $(4,6)$，此时序列变为 $(2,1)$。\n\n然后不删除任何前缀或后缀，之后进行第三次操作，删除后缀 $(1)$，此时序列变为 $(2)$。\n\n然后不删除任何前缀或后缀，之后进行第四次操作，删除唯一剩余的 $(2)$，此时序列变为空序列。\n\n最后一次操作由于序列为空无法完成，操作停止。\n\n因此一共进行了四次操作。\n\n|子任务编号|\t附加限制|\t分值|\n|:-:|:-:|:-:|\n|$0$|\t是样例|\t$0$|\n|$1$|\t$n,q\\le 100$|\t$19$|\n|$2$|\t$d_1=d_2=\\ldots=d_q=1$|\t$28$|\n|$3$|\t无附加限制|\t$53$|"}],"translated_statement":null,"sample_group":[["5 6\n1 2 3 4 5\n1 1\n1 2\n1 3\n1 4\n1 6\n1 5\n","4"],["5 3\n1 3 2 2 1\n3 1\n1 3\n2 2\n","2"],["9 5\n1 3 2 5 1 4 6 2 1\n3 2\n2 3\n1 1\n1 2\n1 1\n","4"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}