{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"After a long series of jobless days, Sherlock and Watson frustated by the lack of new cases, decide to turn their minds toward something interesting like solving few logical problems. One of the problems they have to solve now is as follows:\n\n Given an array \u003cb\u003eA\u003c/b\u003e of size \u003cb\u003eN\u003c/b\u003e and a list of \u003cb\u003eQ\u003c/b\u003e number of queries, where each query has two numbers \u003cb\u003eL\u003c/b\u003e and \u003cb\u003eR\u003c/b\u003e, find for each query the number of inversions in the subarray from \u003cb\u003eL\u003c/b\u003eth to \u003cb\u003eR\u003c/b\u003eth position (both inclusive) of the array \u003cb\u003eA\u003c/b\u003e( array has 1-based index).\n\nFor an array \u003cb\u003eA\u003c/b\u003e two elements \u003cb\u003eA[i]\u003c/b\u003e and \u003cb\u003eA[j]\u003c/b\u003e form an inversion if \u003cb\u003eA[i] \u0026gt; A[j]\u003c/b\u003e and \u003cb\u003ei \u0026lt; j\u003c/b\u003e. Help them to solve this problem. \n\n\n\n\n"}},{"title":"Input","value":{"format":"MD","content":"First line contains a single integer, length \u003cb\u003eN\u003c/b\u003e of the array. \n\nSecond line has \u003cb\u003eN\u003c/b\u003e space separated numbers, where \u003cb\u003eith\u003c/b\u003e element is \u003cb\u003eA[i]\u003c/b\u003e. \nThird line has a single integer \u003cb\u003eQ\u003c/b\u003e.\n\nNext \u003cb\u003eQ\u003c/b\u003e lines have \u003cb\u003e2\u003c/b\u003e space separated integers \u003cb\u003eL\u003c/b\u003e and \u003cb\u003eR\u003c/b\u003e of that query. \n"}},{"title":"Output","value":{"format":"MD","content":"Output \u003cb\u003eQ\u003c/b\u003e lines, \u003cb\u003ei\u003c/b\u003eth line having a single integer, the answer to the \u003cb\u003ei\u003c/b\u003eth query\n"}},{"title":"Example Input","value":{"format":"MD","content":"\u003cpre\u003e7\n7 9 3 5 1 6 4\n4\n1 4\n3 5\n1 2\n1 7\n\u003c/pre\u003e"}},{"title":"Example Output","value":{"format":"MD","content":"\u003cpre\u003e4\n2\n0\n14\n\u003c/pre\u003e"}},{"title":"Constraints","value":{"format":"MD","content":"\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e20000\u003c/b\u003e\n\u003cb\u003e0\u003c/b\u003e ≤ \u003cb\u003eA[i]\u003c/b\u003e ≤ \u003cb\u003e10^9\u003c/b\u003e\n\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eQ\u003c/b\u003e ≤ \u003cb\u003e20000\u003c/b\u003e\n\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eL\u003c/b\u003e ≤ \u003cb\u003eR\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e\n\n"}}]}