{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eFancyCoder once encountered a challenging problem called \"K-th Problem\". Here is the description: given an array of N integers A[1],A[2],...,A[N] and some queries, each query asks for the K-th largest element among A[L],A[L+1],...,A[R]. \r\n\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003e\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003eAfter learning a lot of data structures, FancyCoder finds this problem can be solved effectively by \"Partition Tree\" or \"Persistent Segment Tree\" (alias: \"Chairman Tree\"). \u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0; -qt-paragraph-type: empty;\"\u003e\u003cbr\u003e\u003c/p\u003e\u003cp style\u003d\"margin: 0px; text-indent: 0px; -qt-block-indent: 0;\"\u003eHowever, FancyCoder is still not satisfied. He raises another problem called \"Reverse K-th Problem\". The description is also simple: given an array of N integers A[1],A[2],...,A[n] and some queries, each query asks for the number of continuous subsequences of the array in which the K-th largest element is X.\u003c/p\u003e\u003cp\u003e\u003cbr\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer T (1 \u0026lt;\u003d T \u0026lt;\u003d 5), indicating the number of test cases.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tFor each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThe first line contains two integers N and Q (1 \u0026lt;\u003d N \u0026lt;\u003d 2,000, 1 \u0026lt;\u003d Q \u0026lt;\u003d 2,000,000), indicating there are N integers in the array and Q queries.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThe second line contains N integers between 1 and N, indicating the element of the array.\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tThen Q lines follow, the i-th line contains two integers Ki and Xi (1 \u0026lt;\u003d Ki,Xi \u0026lt;\u003d N), indicating that the i-th query asks for the number of continuous subsequences of the array in which the Ki-th largest element is Xi."}},{"title":"Output","value":{"format":"HTML","content":"For each test case:\u003cbr\u003e\t\t\t\u003cbr\u003e\t\t\tOutput Q lines, the i-th line contains one integer, indicating the answer to the i-th query."}},{"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\u003e2\r\n3 2\r\n1 1 2\r\n1 1\r\n2 1\r\n5 4\r\n1 4 3 2 5\r\n2 3\r\n1 4\r\n4 1\r\n2 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3\r\n5\r\n6\r\n1\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}