No.1435 Mmm......
タグ : / 解いたユーザー数 109
作問者 :
Problem Statement
You are given an integer $N$ and an integer sequence $a_1,a_2,\dots,a_N$.
Find the number of pairs of integers $(l,r)$ satisfying the following conditions.
- $1 \le l < r \le N$
- Let $m_1,m_2,M$ be the first element, the $2$-nd element from the front, and the last element, respectively, when $(a_l,a_{l+1},\dots,a_r)$ is sorted in ascending order. Then $M \le m_1+m_2$.
Constraints
- $N,a_i$ are integers
- $2 \le N \le 2 \times 10^5$
- $1 \le a_i \le 10^9$
Input
$N$
$a_1\ \ a_2\ \dots\ a_N$
The $1$-st line contains the integer $N$, and the $2$-nd line contains the integer sequence $a_1,a_2,\dots,a_N$ separated by spaces.
Output
Print the number of pairs of integers $(l,r)$ satisfying the conditions on $1$ line. Print a newline at the end.
Sample
Sample 1
Input
5
2 2 5 2 4
Output
5
The pairs are $(l,r)=(1,2),(2,3),(3,4),(3,5),(4,5)$.
For example, when $(l,r)=(3,5)$, we have $m_1=2,m_2=4,M=5$, which satisfies the condition.
When $(l,r)=(1,4)$, we have $m_1=2,m_2=2,M=5$, which does not satisfy the condition.
When $(l,r)=(1,2)$, we have $m_1=2,m_2=2,M=2$, which satisfies the condition.
Sample 2
Input
5
1 2 3 4 5
Output
8
The pairs are $(l,r)=(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)$.
Sample 3
Input
3
1 1 1
Output
3
Sample 4
Input
20
14 7 11 17 6 3 18 15 6 7 19 15 7 7 5 9 19 18 14 16
Output
36
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。