問題一覧 > 通常問題

No.1371 Swap Kadomatsu Sequence: Matsu

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 31
作問者 : mai / テスター : 夕叢霧香(ゆうむらきりか)
お気に入りにしたユーザー ProblemId : 3411 / 自分の提出
問題文最終更新日: 2020-11-13 12:47:27
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 280 (門松コンテスト) (順位表) の他の問題:

Definition

A sequence of 3 elements $v = (a_1,a_2,a_3)$ is, according to tradition, called a Kadomatsu sequence when $v$ satisfies the following conditions.

  1. $a_1,a_2,a_3$ are all distinct
  2. Among the 3 elements, $a_2$ is the largest or the smallest

Furthermore, when a sequence $w = (a_1,...,a_n)$ of $n$ elements (where $3\le n$) is such that
any 3 consecutive elements taken from it form a Kadomatsu sequence, $w$ is called a Kadomatsu sequence sequence.

Problem Statement

You are given a permutation of length $N$.
Mysteriously, this permutation has already been rearranged into a Kadomatsu sequence sequence by someone.

Yukikodera-san wondered whether it could remain a Kadomatsu sequence sequence even after swapping some two elements.

Output the number of pairs $i$ and $j$ ( $i\lt j$ ) such that the sequence is still a Kadomatsu sequence sequence after swapping the $i$-th and $j$-th elements.

Input

$N$
$A_1\ \ldots\ A_N$

$5 \le N \le 2\times 10^5$
$1 \le A_i \le N$
$A_i \neq A_j\ (i\neq j)$

All inputs are integers.
$A$ is a Kadomatsu sequence sequence.

Output

Output the number of possible pairs $(i,j)$.

Print a newline at the end.

Sample

Sample 1
Input
6
1 4 2 5 3 6
Output
7

The following 7 ways are possible.

  • Swap the 1st and 3rd elements.
  • Swap the 1st and 5th elements.
  • Swap the 2nd and 4th elements.
  • Swap the 2nd and 5th elements.
  • Swap the 2nd and 6th elements.
  • Swap the 3rd and 5th elements.
  • Swap the 4th and 6th elements.
Sample 2
Input
5
1 3 2 5 4
Output
2

The possible $(i,j)$ are the 2 pairs (1,3), (2,5).

Sample 3
Input
15
5 10 6 9 7 12 1 14 8 13 11 15 3 4 2
Output
37

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