Air Raid Shelter

Time limit1sMemory limit1024 MB

Summary

Given N unit square walls, find the largest area of interior space that the walls can fully enclose.

Level: Medium6 of 10
Topics: Math, Implementation
Solved: No attempts yet

문제

Build the largest possible air raid shelter by placing $N$ walls, each a square with side length $1$ , parallel to each other's sides and without overlapping. The area of a shelter is the floor area of the interior space fully enclosed by the walls. Find the maximum area of a shelter that can be made from $N$ walls.

With $7$ walls placed as shown below, you can make a shelter with area $3$ . No shelter with a larger area can be made.

입력

The first line contains the number of walls $N$ . $\left(1\leq N\leq 10,000,000\right)$

출력

Print the maximum area of a shelter that can be made from $N$ walls.

Examples4

Example 1
Input
```
4
```
Expected output
```
1
```
Example 2
Input
```
5
```
Expected output
```
1
```
Example 3
Input
```
6
```
Expected output
```
2
```
Example 4
Input
```
7
```
Expected output
```
3
```