solved.ac Grand Arena Party × NEXON (onsite, rated)

$i$번째 수부터 $j$번째 수까지가 오름차순으로 배열되어있기 위해서는, $i \le k < j$를 만족하는 모든 정수 $k$에 대해 $A_k < A_{k+1}$을 만족해야 합니다. 조건은 인접한 두 수를 비교하는 것만으로 판단할 수 있습니다. 즉, $B_k$를 $A_k < A_{k+1}$을 만족하는지 여부에따라 True 혹은 False로 나타내면, $i$번째 수부터 $j$번째 수까지가 오름차순이라는 것은, $B_i, B_{i+1}, \cdots, B_{j-1}$ 모두가 True라는 것입니다.

이런 $(i, j)$를 세는 방법은 여러가지가 있습니다.

• $i = j$ 인 경우에는 항상 오름차순으로 나열되어 있기 때문에, 경우의 수는 기본적으로 $N$이 됩니다.
• $i \ne j$는 연속된 True의 블럭을 생각해봅시다. 이 블럭 내부에서 아무렇게나 시작점과 끝점을 잡는 것이 됩니다. 블럭의 길이가 $k$이라면, 서로 다른 두 시작점과 끝점을 잡는 경우의 수는 $\frac{k(k+1)}{2}$입니다.

답은 $B$에서 연속된 True 블럭 길이 $k$에 대해 $\frac{k(k+1)}{2}$를 모두 더한 것에 $N$을 더한 것이 됩니다. 모든 연산은 $\mathcal O (N)$에 처리할 수 있습니다.