Consider the condition that a building can been seen from both buildings \(l\) and \(r\) \((l<r)\). Obvious necessary conditions are:

1. It can be seen from building \(l\).
2. It it to the east of building \(r\).

These are actually sufficient conditions.

(Proof) If building \(x\) \((x>r)\) can be seen from building \(l\), then \(H_k < H_x\) for all \(k\ (l<k<x)\) by definition. Thus, \(H_k < H_x\) holds for all \(k\ (r<k<x)\), and building \(x\) can be seen from building \(r\).

All that left is to count such building. As described in the editorial of ABC372-D(Buildings), the set of buildings that can be seen from building \(l\) can be managed in a stack. In the original problem, we can prefetch the queries; when we are maintaining the set of buildings that can be seen from building \(l\), we just need to be able to count the elements greater than \(r\). This can be done with a Fenwick tree or binary search.

(Fenwick tree)

from atcoder.fenwicktree import FenwickTree

n, q = map(int, input().split())
h = list(map(int, input().split()))
query = [[] for i in range(n)]
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query[l].append((r, i))

ft = FenwickTree(n)
stc = []
ans = [0] * q
for l in range(n - 1, -1, -1):
    for r, i in query[l]:
        ans[i] = ft.sum(r + 1, n)
    while stc and h[stc[-1]] < h[l]:
        ft.add(stc.pop(), -1)
    stc.append(l)
    ft.add(l, 1)
print(*ans, sep="\n")

(Binary search)

import bisect
n, q = map(int, input().split())
h = list(map(int, input().split()))
query = [[] for i in range(n)]
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query[l].append((r, i))
ans = [0] * q
stc = []
for l in range(n - 1, -1, -1):
    for r, i in query[l]:
        ans[i] = bisect.bisect_left(stc, -r)
    while stc and h[-stc[-1]] < h[l]:
        stc.pop()
    stc.append(-l)
print(*ans, sep="\n")