次の 3 種類の連続部分列の個数を数えるために、以下の DP 配列を定義する：

• \(dp_i\): 添字 \(i\) を終点とする連続増加部分列（長さ 2以上）の個数
• \(dp\_id_i\): 添字 \(i\) を終点とする「山型」部分列（長さ 3 以上）の個数
  
  • 山型とは、長さが 3 以上で、先頭が増加し、途中に唯一の極大点 \(A_{j-1} < A_j > A_{j+1}\) を持って、極小点 \(A_{j-1} > A_j < A_{j+1}\) を持たないようなもの
• \(dp\_idi_i\): 添字 \(i\) を終点とする「チルダ型」部分列の個数

数列 \(A\) の各要素について、以下のように状態を更新する：

• \(A_i < A_{i-1}\) のとき：

  • \( dp\_id_i = dp_{i-1} + dp\_id_{i-1} \)

  • \(dp_i, dp\_idi_i=0\)

• \(A_i > A_{i-1}\) のとき：

  • \(dp_i = dp_{i-1} + 1\)

  • \(dp\_idi_i = dp\_id_{i-1} + dp\_idi_{i-1}\)

  • \(dp\_id_i=0\)

答え \(\sum_{i=0}^{N-1} dp\_idi_i\) が \(O(N)\) の時間で得られる。