Three at the Top - Repovive Premier Round 7 | Repovive

20G. Three at the Top

3500 pts2s256 MB

You are given a permutation $p_1,p_2,\ldots,p_n$ .

You must color every position with one of three colors: red, green, or blue.

A coloring is called valid if the following condition holds for every subarray of length at least $2$ :

the positions containing the largest and the second-largest values in the subarray have different colors.

The score of a valid coloring is the number of subarrays of length at least $3$ in which the positions containing the three largest values have pairwise different colors.

Find the maximum possible score of a valid coloring.

Constraints

$1 \le n \le 2 \times 10^5$
$p$ is a permutation of $1,2,\ldots,n$

Input

\begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array}

Output

ans

Samples

Input

1
1

Explanation

There is no subarray of length at least $3$ , so every valid coloring has score $0$ .

Output

Input

4
2 1 3 4

Explanation

Coloring positions $1,2,3,4$ red, green, blue, red is valid. The subarrays $[1,3]$ and $[2,4]$ contribute to its score.

In every valid coloring, positions $1,2,3$ have pairwise different colors. Position $4$ must differ from position $3$ , so at least one of $[2,4]$ and $[1,4]$ cannot contribute. Therefore, a score greater than $2$ is impossible.

Output

Input

5
1 2 3 4 5

Explanation

Color the positions red, green, blue, red, green, in this order. This coloring is valid, and every subarray of length at least $3$ contributes to its score. There are $6$ such subarrays, so no larger score is possible.

Output

You are given a permutation $p_1,p_2,\ldots,p_n$ .

You must color every position with one of three colors: red, green, or blue.

A coloring is called valid if the following condition holds for every subarray of length at least $2$ :

the positions containing the largest and the second-largest values in the subarray have different colors.

The score of a valid coloring is the number of subarrays of length at least $3$ in which the positions containing the three largest values have pairwise different colors.

Find the maximum possible score of a valid coloring.

$1 \le n \le 2 \times 10^5$
$p$ is a permutation of $1,2,\ldots,n$

\begin{array}{l} n \\ p_1 \quad p_2 \quad \cdots \quad p_n \end{array}

ans

There is no subarray of length at least $3$ , so every valid coloring has score $0$ .

Coloring positions $1,2,3,4$ red, green, blue, red is valid. The subarrays $[1,3]$ and $[2,4]$ contribute to its score.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

20G. Three at the Top

Constraints

Input

Output

Samples

20G. Three at the Top

Constraints

Input

Output

Samples