A function F(l, r) is defined as follow:

F(l, r) = 0 if l > r

else m is the index of the largest element from l to r.

F(l, r) = r — l + 1 + F(l, m — 1) + F(m + 1, r)

Given a permutation of length N and Q queries (l, r), calculate F(l, r) for each queries.

N <= 1e6, Q <= 1e6

Thanks!