在城市的一条主干道旁，有 n 座连续的建筑，每座建筑有一个高度。站在一座建筑的顶端，只能看到它左边比它矮的建筑顶部。如果遇到一座高度大于或等于它的建筑，就无法继续看到更左边的建筑顶部。

城市规划部门会进行 M 次调查，每次调查区间 [L, R] 内所有建筑的视野总和，即每座建筑能看到的左边建筑的数量之和。

视野定义：对于位置 i，它能看到的建筑数量 = 它左边第一个比它矮的建筑是否存在（1 或 0）。即如果存在左边第一个比它矮的建筑，则看到 1 座，否则看到 0 座。

• 第一行：一个整数 n（n ≤ 10^6），表示建筑的数量。
• 第二行：n 个整数，表示从左到右每座建筑的高度。
• 第三行：一个整数 M（M ≤ 10^6），表示调查次数。
• 接下来 M 行，每行两个整数 L, R（1 ≤ L ≤ R ≤ n），表示一次调查的区间。

• 对于每个调查，输出区间 [L, R] 内所有建筑能看到的左边建筑数量的总和。

建筑高度：[3, 2, 4, 1, 5]

• 建筑 1（高 3）：左边没有建筑，看到 0 座。
• 建筑 2（高 2）：左边建筑 3 比它高，看不到，看到 0 座。
• 建筑 3（高 4）：左边建筑 3、2 比它矮，看到 2 座。
• 建筑 4（高 1）：左边建筑 4 比它高，看不到，看到 0 座。
• 建筑 5（高 5）：左边建筑全部比它矮，看到 4 座。

区间 [1, 3]：0 + 0 + 2 = 2
区间 [2, 4]：0 + 2 + 0 = 2
区间 [1, 5]：0 + 0 + 2 + 0 + 4 = 6

数据范围

• 1 ≤ n ≤ 10^6
• 1 ≤ M ≤ 10^6
• 建筑高度为不超过 10^6 的正整数

单调栈、前缀和