問題一覧 > 通常問題

No.1435 Mmm......

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 79
作問者 : tyawanmusityawanmusi / テスター : yuto1115yuto1115
9 ProblemId : 5401 / 出題時の順位表
問題文最終更新日: 2021-02-25 04:59:18

問題文

整数 $N$ と整数列 $a_1,a_2,\dots,a_N$ が与えられます。

以下の条件を満たす整数の組 $(l,r)$ の個数を求めてください。

  • $1 \le l < r \le N$
  • $(a_l,a_{l+1},\dots,a_r)$ を昇順ソートしたときの先頭の要素、先頭から $2$ 番目の要素、末尾の要素をそれぞれ $m_1,m_2,M$ としたとき、$M \le m_1+m_2$

制約

  • $N,a_i$ は整数
  • $2 \le N \le 2 \times 10^5$
  • $1 \le a_i \le 10^9$

入力

$N$
$a_1\ \ a_2\ \dots\ a_N$

$1$ 行目には整数 $N$ が、$2$ 行目には整数列 $a_1,a_2,\dots,a_N$ が空白区切りで入力されます。

出力

条件を満たす整数の組 $(l,r)$ の個数を $1$ 行に出力してください。 最後に改行してください。

サンプル

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

$(l,r)=(1,2),(2,3),(3,4),(3,5),(4,5)$ です。

例えば $(l,r)=(3,5)$ のとき、 $m_1=2,m_2=4,M=5$ と条件を満たします。

$(l,r)=(1,4)$ のとき、 $m_1=2,m_2=2,M=5$ と条件を満たしません。

$(l,r)=(1,2)$ のとき、 $m_1=2,m_2=2,M=2$ と条件を満たします。

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

$(l,r)=(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$ です。

サンプル3
入力
3
1 1 1
出力
3
サンプル4
入力
20
14 7 11 17 6 3 18 15 6 7 19 15 7 7 5 9 19 18 14 16
出力
36

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