{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e\n There is an apple tree in front of Taotao\u0027s house. When autumn comes, $n$ apples on the tree ripen, and Taotao will go to pick these apples.\u003cbr\u003e\u003cbr\u003e\n When Taotao picks apples, Taotao scans these apples from the first one to the last one. If the current apple is the first apple, or it is strictly higher than the previously picked one, then Taotao will pick this apple; otherwise, he will not pick.\u003cbr\u003e\u003cbr\u003e\n Given the heights of these apples $h_1, h_2, \\cdots, h_n$, you are required to answer some independent queries. Each query is two integers $p, q$, which asks the number of apples Taotao would pick, if the height of the $p$-th apple were $q$ (instead of $h_p$). Can you answer all these queries?\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input is a single line of integer $T$ $(1 \\leq T \\leq 10)$, the number of test cases.\u003cbr\u003e\u003cbr\u003e\nEach test case begins with a line of two integers $n, m$ $(1 \\leq n, m \\leq 10^5)$, denoting the number of apples and the number of queries. It is then followed by a single line of $n$ integers $h_1, h_2, \\cdots, h_n$ $(1 \\leq h_i \\leq 10^9)$, denoting the heights of the apples. The next $m$ lines give the queries. Each of these $m$ lines contains two integers $p$ $(1 \\leq p \\leq n)$ and $q$ $(1 \\leq q \\leq 10^9)$, as described in the problem statement."}},{"title":"Output","value":{"format":"HTML","content":"For each query, display the answer in a single line."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e1\r\n5 3\r\n1 2 3 4 4\r\n1 5\r\n5 5\r\n2 3\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\u003cpre\u003e1\r\n5\r\n3\u003c/pre\u003e\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e\nFor the first query, the heights of the apples were 5, 2, 3, 4, 4, so Taotao would only pick the first apple.\u003cbr\u003e\u003cbr\u003e\nFor the second query, the heights of the apples were 1, 2, 3, 4, 5, so Taotao would pick all these five apples.\u003cbr\u003e\u003cbr\u003e\nFor the third query, the heights of the apples were 1, 3, 3, 4, 4, so Taotao would pick the first, the second and the fourth apples.\u003cbr\u003e"}}]}