Segments

Time limit1sMemory limit128 MB

Summary

Given n disjoint vertical segments, find the maximum possible number of pairs that can see each other via an unobstructed horizontal segment.

Level: Hard8 of 10
Topics: Geometry, Combinatorics, Greedy
Solved: No attempts yet

Problem

Consider a set $S$ of $n$ vertical segments in the plane (each segment includes its two endpoints). No two segments of $S$ have a point in common.

Two segments see each other if there is a horizontal segment that joins them and has no point in common with any other segment of $S$ .

The figure below shows an example set of segments. The pairs of segments that see each other are 1-2, 1-3, 2-3, 1-5, and 4-5. Segments 1 and 4 do not see each other.

Among all sets of exactly $n$ pairwise disjoint vertical segments, we look for the largest possible number of pairs of segments that see each other. Given $n$ , compute this maximum number of visible pairs.

Input

The only line of input contains one integer $n$ ( $1 \le n \le 20\,000$ ).

Output

Print one integer: the maximum possible number of pairs of segments that can see each other, taken over all sets of $n$ pairwise disjoint vertical segments.

Hint

Examples4

Example 1
Input
```
1
```
Expected output
```
0
```
Example 2
Input
```
2
```
Expected output
```
1
```
Example 3
Input
```
3
```
Expected output
```
3
```
Example 4
Input
```
4
```
Expected output
```
6
```