問題一覧 > 通常問題

No.1435 Mmm......

レベル : / AI推定難易度 : 1475 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 109
作問者 : tyawanmusi / テスター : yuto1115
お気に入りにしたユーザー ProblemId : 5401 / 自分の提出
問題文最終更新日: 2021-02-25 04:59:18
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 287 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。