Description

And the seasons they go round and round
And the painted ponies go up and down
We're captive on the carousel of time
We can't return, we can only look behind from where we came
And go round and round and round in the circle game...

-- Joni Mitchell, The Circle Game

One day, vv123 thought of the days when he played circle game with his classmates in PE class, when he was just an elementary school student.

There are $n$ ($n$ is even) kids forming a circle hand by hand, the strength of the $n$ kids are $1,2,\ldots,n$ respectively. vv123 wants to rearrange the kids in the circle, so that the circle is firmest.

Suppose that the villain can only attack half the circle at a time, and it will obviously attack the weakest part of the circle. So, we define the firmness of the circle as the smallest sum of any $\frac{n}{2}$ consecutive kids' strength.

For the given $n$, what's the maximum firmness that can be achieved?

Input

An integer $n$ ($2\le n \le 10000$). It is guaranteed that $n$ is even.

Output

An integer, denoting the maximum firmness that can be achieved.

Samples

4

4

6

10

Note

In the first example, $n = 4$, there are $6$ ways to form the circle:

• $1-2-3-4-1$, the firmness is $\min (1+2,2+3,3+4,4+1) = 3$.
• $1-2-4-3-1$, the firmness is $\min (1+2,2+4,4+3,3+1) = 3$.
• $1-3-2-4-1$, the firmness is $\min (1+3,3+2,2+4,4+1) = 4$.
• $1-3-4-2-1$, the firmness is $\min (1+3,3+4,4+2,2+1) = 3$.
• $1-4-2-3-1$, the firmness is $\min (1+4,4+2,2+3,3+1) = 4$.
• $1-4-3-2-1$, the firmness is $\min (1+4,4+3,3+2,2+1) = 3$.

So, the maximum firmness that can be achieved is $4$.

In the second example, there are $120$ ways to form the circle. The maximum firmness that can be achieved is $10$, and one possible way to achieve this is $1-4-5-2-3-6-1$.

Resources

电子科技大学第十三届 ACM 趣味程序设计竞赛