L. Left or right side
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The organizers of the São Paulo Programming Contest decided to create a special system to control the entry of teams into the competition area. There are $$$N$$$ teams registered for the contest, each with a unique identifier between $$$0$$$ and $$$N - 1$$$.

To organize the flow of participants, a network of checkpoints is built. Each checkpoint has a distinct number $$$v$$$ between $$$0$$$ and $$$N - 1$$$ and may have a corridor to the left and/or a corridor to the right, thus having $$$0$$$, $$$1$$$, or $$$2$$$ corridors in total.

The checkpoint structure must satisfy the following property: for every checkpoint numbered $$$v$$$, all checkpoints reachable through its left corridor have numbers smaller than $$$v$$$, while all checkpoints reachable through its right corridor have numbers greater than $$$v$$$.

The goal of each team is to reach the checkpoint whose number matches its identifier. When a team arrives at a checkpoint numbered $$$v$$$, its identifier $$$id$$$ is compared with $$$v$$$:

  • if $$$id \lt v$$$, the team proceeds through the left corridor;
  • if $$$id \gt v$$$, the team proceeds through the right corridor;
  • if $$$id = v$$$, the team remains at that checkpoint.

Each corridor leads to another checkpoint, where the same process is repeated. Thus, a team may pass through several checkpoints before reaching its final destination.

During the day, the teams arrive in the order specified by a sequence $$$P$$$. To analyze the efficiency of a particular checkpoint $$$u$$$, only the teams that pass through it without remaining there are considered. For each such team:

  • record E if it is sent through the left corridor of $$$u$$$;
  • record D if it is sent through the right corridor of $$$u$$$.

This produces a sequence $$$S$$$ consisting of the characters E and D. The contribution of a checkpoint is the number of adjacent pairs of positions whose characters are different. In other words, the number of positions $$$i$$$ such that $$$S_i \neq S_{i+1}$$$.

The total score of the system is the sum of the contributions of all checkpoints.

Rouse knows the sequence $$$P$$$ and wants to determine the maximum possible total score that can be achieved by choosing the best possible checkpoint structure. Can you help her?

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 500$$$), the number of teams.

The second line contains $$$N$$$ distinct integers $$$P_1, \ldots, P_N$$$ ($$$0 \le P_i \lt N$$$), representing the order in which the teams arrive.

Output

Your program must output a single line containing the maximum possible total score among all valid checkpoint structures.

Examples
Input
7
0 4 2 6 1 5 3
Output
7
Input
5
4 3 1 2 0
Output
2
Note

Explanation of Sample 1:

Rouse chooses the following checkpoint structure.

The checkpoint contributions are as follows:

  • At checkpoint $$$1$$$, the teams with identifiers $$$0$$$ and $$$2$$$ pass through it, generating the sequence ED. Since there is one change between consecutive characters, its contribution is $$$1$$$.
  • At checkpoint $$$3$$$, the teams with identifiers $$$0$$$, $$$1$$$, $$$2$$$, $$$4$$$, $$$5$$$, and $$$6$$$ pass through it, generating the sequence EDEDED. Since there are $$$5$$$ changes between consecutive characters, its contribution is $$$5$$$.
  • At checkpoint $$$5$$$, the teams with identifiers $$$4$$$ and $$$6$$$ pass through it, generating the sequence ED. Since there is one change between consecutive characters, its contribution is $$$1$$$.

The other checkpoints have contribution $$$0$$$, since no team passes through them. Therefore, the maximum total contribution is $$$7$$$.

Explanation of Sample 2:

Rouse chooses the following checkpoint structure.

The checkpoint contributions are as follows:

  • At checkpoint $$$1$$$, the teams with identifiers $$$0$$$ and $$$2$$$ pass through it, generating the sequence DE. Since there is one change between consecutive characters, its contribution is $$$1$$$.
  • At checkpoint $$$3$$$, the teams with identifiers $$$0$$$, $$$1$$$, $$$2$$$, and $$$4$$$ pass through it, generating the sequence DEEE. Since there is only one change between consecutive characters, its contribution is $$$1$$$.

The other checkpoints have contribution $$$0$$$, since no team passes through them. Therefore, the maximum total contribution is $$$2$$$.