問題一覧 > 通常問題

No.121 傾向と対策:門松列(その2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 40
作問者 : LayCurseLayCurse
2 ProblemId : 292 / 出題時の順位表
問題文最終更新日: 2016-05-24 14:36:29

問題文

ここ数日で門松列に関する問題が頻出しております.
ここでは演習を通じて,門松列に対する理解を深め,門松列の問題が出題された時に解けるようになっておきましょう.
門松列対策講座を受講される皆様は既にご存知かと思いますが,門松列とは $3$ 個の要素からなる数列 $a,b,c$ で以下の $2$ つの条件を満たすものです.
・$a,b,c$ は全て異なる
・$3$ つの要素の中で $b$ が最も大きい,または,$b$ が最も小さい

さて,友紀さんは $N$ 要素の整数列 $A_1,A_2,\ldots,A_N$ を持っています.
友紀さんはこの配列の部分列として,門松列が何箇所出現するかを知りたいと思っています.
門松列の数を求めるプログラムを書いてください.
つまり,以下の条件を満たす整数の $3$ つ組 $(i,j,k)$ の数を求めるプログラムを書いてください.
・$1 \leq i < j < k \leq N$ かつ $A_i,A_j,A_k$ が門松列

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

$1 \leq N \leq 1000000 = 10^6$
$1 \leq A_k \leq 1000000000 = 10^9$

出力

答えを $1$ 行で出力してください.

サンプル

サンプル1
入力
5
1 4 2 5 2
出力
5

以下の $5$ 箇所存在します:
・$(i,j,k) = (1,2,3)$ の時,$(A_i,A_j,A_k) = (1,4,2)$
・$(i,j,k) = (1,2,5)$ の時,$(A_i,A_j,A_k) = (1,4,2)$
・$(i,j,k) = (1,4,5)$ の時,$(A_i,A_j,A_k) = (1,5,2)$
・$(i,j,k) = (2,3,4)$ の時,$(A_i,A_j,A_k) = (4,2,5)$
・$(i,j,k) = (2,4,5)$ の時,$(A_i,A_j,A_k) = (4,5,2)$
門松列として $1,4,2$ が $2$ 個含まれますが,場所が違うので両方カウントします.

サンプル2
入力
2
1 1
出力
0

長さ $3$ の部分列がそもそも存在しませんね.

サンプル3
入力
35
1 3 5 5 4 3 5 5 5 3 3 4 2 5 4 4 3 2 3 1 3 1 5 1 5 1 2 1 5 2 4 1 4 2 1
出力
2015

新年あけましておめでとうございます.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。