First of all, the problem can be solved in a total of \(\mathrm{O}(N^3)\) or \(\mathrm{O}(N^2)\) time by naively bruteforcing \(L\) and \(R\), but it will result in TLE (Time Limit Exceeded) as \(N \leq 2\times 10^5\). So we will introduce the way to solve this problem in a total of \(\mathrm{O}(N)\) using a proper algorithm.

First, although this problem asks to find the number of pairs of integers \((L,R)\) that satisfy certain condition, but from another point of view, it can be rephrased as follows.

How many consecutive subsequences \(A_{L}, A_{L+1}, \dots, A_{R}\) of \(A\) have the maximum value \(X\) and the minimum value \(Y\)?

Transforming the problem on counting \((L,R)\) into that of counting segments makes easier to break down.
However, the problem is still troublesome, so let us take a closer look at what kind of consecutive subsequences satisfy the condition in order to simply the problem. Consider the following case:

\[A = (4,2,5,4,3,4,2), X=4, Y=2\]

In this example, \(A_3 = 5\) is troublesome. Since \(A_3 = 5\) is greater than \(X = 4\), any consecutive subsequences that contains \(A_3\) does not satisfy the condition. Such an element imposes us a rather complex case division.
On the second thought, as any consecutive subsequences that contains \(A_3\) does not satisfy the condition, we can just remove \(A_3\) from the sequence and split it off at that element, and count the number of subsequences for each sequences. That is, letting \(A_1\) the first two element and \(A_2\) the last four elements, we can solve the problem for the following two cases:

\[ A_1 = (4, 2), X=4, Y=2\]

\[A_2 = (4,3,4,2), X=4, Y=2\]

and then find the sum to obtain the overall answer.

This is the same in a general case. If \(A_i\) does not satisfy \(X \leq A_i \leq Y\), we may remove \(A_i\) to split the sequence off, and find the number for each subsequences.

Let \(B\) be a sequence that was split off by the operation above. All we have to solve is the following Subproblem 1.

Subproblem 1

How many consecutive subsequences \(B_{L}, B_{L+1}, \dots, B_{R}\) of \(B\) has the maximum value \(X\) and the minimum value \(Y\)? Here, each element of \(B\) is between \(Y\) and \(X\) (inclusive).

The condition emphasized by boldface is added compared to the original problem. In fact, we can make use of this condition to further rephrase the subproblem. As we know that each element is between \(Y\) and \(X\), “the maximum and minimum value is \(X\) and \(Y\), respectively” if and only if “\(X\) and \(Y\) are both contained in the subsequence.” Therefore, it is sufficient to solve the following subproblem fast enough:

Subproblem 2

How many consecutive subsequences \(B_{L}, B_{L+1}, \dots, B_{R}\) of \(B\) contains both \(X\) and \(Y\)?

If we can solve the problem in a linear time, that is, in \(\mathrm{O}(|B|)\) time, then the overall complexity will be \(\mathrm{O}(\sum_{B \in (\text{the set of divided subsequences of }A)} B) = \mathrm{O}(N)\), as the sum of lengths of subsequences does not exceed \(N\).

There are several ways to solve Subproblem 2. We will introduce it one by one.

Solution 1: sliding windows

Hereinafter we denote \(B_L,B_{L+1},\dots,B_R\) by “segment \([L,R]\).”

In Subproblem 2, the following property holds:

If segment \([k,l]\) contains \([i,j]\), that is, if \(i,j,k\), and \(l\) satisfy \(1 \leq k \leq i \leq j \leq l \leq |B|\), then if segment \([i,j]\) satisfies the condition, \([k, l]\) also satisfies the condition.

In this case, we can count the number of segments that satisfy the condition by the following algorithm.

• First, let \(L=R=1\).
• While \(L\) does not exceed \(N\), do the following operation.
  • While \([L,R]\) does not satisfy the condition, add \(1\) to \(R\).
  • Once a \([L,R]\) that satisfies the condition has been found, we know that every segment \([L,x]\) \((R\leq x \leq B)\) satisfy the condition, so add that amount to the answer.
  • Add \(1\) to \(L\).

The algorithm of iterating through all minimal segments by sliding the both ends one by one like this is called “sliding window” trick. Since the number of times that \(L\) and \(R\) are incremented is bounded by \(|B|\), the total complexity is \(\mathrm{O}(|B|)\) if the condition is judged in an \(\mathrm{O}(1)\) time each.

The following is a sample code in Python.

N, X, Y = map(int, input().split())
A = list(map(int, input().split()))

def calc(B):
  i, j, countX, countY, res = 0, 0, 0, 0, 0
  while i != len(B):
    while j != len(B) and (countX == 0 or countY == 0):
      if B[j] == X:
        countX += 1
      if B[j] == Y:
        countY += 1
      j += 1
    if countX > 0 and countY > 0:
      res += len(B) + 1 - j
    if B[i] == X:
      countX -= 1
    if B[i] == Y:
      countY -= 1
    i += 1
  return res


i, ans = 0, 0
while i != N:
  B = []
  while i != N and Y <= A[i] <= X:
    B.append(A[i])
    i += 1
  if len(B) != 0:
    ans += calc(B)
  else:
    i += 1
print(ans)

Solution 2: inclusion-exclusion principle

Another model solution is that of using inclusion-exclusion principle.
Inclusion-exclusion principle is very frequently used in combinatorics problems. Especially, when there are two conditions, the following two equations are well known.

\[ \begin{aligned} &(\text{The set where at least one of }P\text{ and }Q\text{ is true}) \\ &=(\text{The set where }P\text{is true}) + (\text{The set where }Q\text{ is true})-(\text{The set where both }P\text{ and }Q\text{ are true}) \end{aligned} \]

\[ \begin{aligned} &(\text{The set where both }P\text{ and }Q\text{ are true}) \\ &=(\text{The entire set}) - (\text{The set where }P\text{ is true}) - (\text{The set where }Q\text{ is true}) + (\text{The set where both }P\text{ and }Q\text{ are true}) \end{aligned} \]

If you remember the high school class of “set and logic,” it may be easier to understand using Venn’s diagram.

What we want to find is the number of subsequences that “contains both \(X\) and \(Y\).” By applying inclusion-exclusion principle to this condition, it can be represented as follows:

\[ \begin{aligned} &(\text{All sequences})\\ &-(\text{Sequences that does not contain }X)\\ &-(\text{Sequences that does not contain }Y)\\ &+(\text{Sequences that contains neither }X\text{ or }Y).\\ \end{aligned} \]

In fact, “sequences not containing blah blah” is easier to count than “sequences containing blah blah,” so the problem can be solved by applying inclusion-exclusion principle like this. (For details, refer to the sample code.) The time complexity is \(\mathrm{O}(|B|)\).

def f(a):
  ret, s = 0, 0
  for x in a:
    if x == 1:
      ret += s * (s + 1) // 2
      s = 0
    else:
      s += 1
  ret += s * (s + 1) // 2
  return ret


N, X, Y = map(int, input().split())
A = list(map(int, input().split()))
__, X_, _Y, XY = [0] * N, [0] * N, [0] * N, [0] * N

for i in range(N):
  if not (Y <= A[i] and A[i] <= X):
    __[i], X_[i], _Y[i], XY[i] = 1, 1, 1, 1
  if A[i] == X:
    X_[i], XY[i] = 1, 1
  if A[i] == Y:
    _Y[i], XY[i] = 1, 1

print(f(__) - f(X_) - f(_Y) + f(XY))

Alternatively, the problem can be solved with the following \(\mathrm{O}(N \log N)\) solution, which is a bit inferior to the solutions mentioned before, but is still fast enough to get AC (accepted).

• It is sufficient if we can process the query of form “where is the first occurrence of \(X\) and \(Y\) to the right of \(i\)?” for all \(i\). This can be processed in an \(\mathrm{O}(\log N)\) time for each query by storing the positions of occurrences of \(X\) and \(Y\) with cumulative sums or segment tree and doing binary search against them, or storing in std::map and using lower_bound.