No.1435 Mmm......
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 100
作問者 :
tyawanmusi
/ テスター :
yuto1115
タグ : / 解いたユーザー数 100
作問者 :
tyawanmusi
/ テスター :
yuto1115
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。