#include #include #include #include #include #include #include #include #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) #define whole(f,x,...) ([&](decltype((x)) y) { return (f)(begin(y), end(y), ## __VA_ARGS__); })(x) using namespace std; template struct segment_tree { // on monoid int n; vector a; function append; // associative T unit; template segment_tree(int a_n, T a_unit, F a_append) { n = pow(2,ceil(log2(a_n))); a.resize(2*n-1, a_unit); unit = a_unit; append = a_append; } void point_update(int i, T z) { a[i+n-1] = z; for (i = (i+n)/2; i > 0; i /= 2) { a[i-1] = append(a[2*i-1], a[2*i]); } } T range_concat(int l, int r) { return range_concat(0, 0, n, l, r); } T range_concat(int i, int il, int ir, int l, int r) { if (l <= il and ir <= r) { return a[i]; } else if (ir <= l or r <= il) { return unit; } else { return append( range_concat(2*i+1, il, (il+ir)/2, l, r), range_concat(2*i+2, (il+ir)/2, ir, l, r)); } } }; map count_kadomatsu(vector const & a, int first, int last) { int n = a.size(); int direction = first < last ? 1 : -1; map acc; acc[first] = 0; map > que; repeat (i,n) que[direction * a[i]].push_back(i); segment_tree segtree(n, 0, plus()); for (auto & it : que) { int ai; vector is; tie(ai, is) = it; ai *= direction; int cnt = acc[first]; first = ai; for (int i : is) { for (auto & jt : que) { if (jt.first * direction == ai) break; int l = whole(lower_bound, jt.second, i) - jt.second.begin(); int r = jt.second.size() - l; cnt -= l * r; } int l = segtree.range_concat(0, i); int r = segtree.range_concat(i+1, n); cnt += l * r; } for (int i : is) { segtree.point_update(i, 1); } acc[ai] = cnt; } acc[last] = acc[first]; return acc; } int main() { // input int n; scanf("%d", &n); vector a(n); repeat (i,n) scanf("%d", &a[i]); // compute map acch = count_kadomatsu(a, -1, 1e9+7); // a1 < a2, a2 > a3 map accl = count_kadomatsu(a, 1e9+7, -1); // a1 > a2, a2 < a3 // output int q; scanf("%d", &q); while (q --) { int l, h; scanf("%d%d", &l, &h); int hr = (-- acch.upper_bound(h ))->second; int hl = (-- acch.upper_bound(l-1))->second; int lr = ( accl.lower_bound(h+1))->second; int ll = ( accl.lower_bound(l ))->second; printf("%d\n", hr - hl + ll - lr); } return 0; }