Super Shy (Easy)

Time limit1sMemory limit1024 MB

Summary

Given N seats, people sit one at a time, each taking a seat that maximizes the distance to the nearest seated person. Find the largest number of people who can be seated.

Level: Medium5 of 10
Topics: Dynamic programming, Greedy
Solved: No attempts yet

Problem

There are $N$ empty seats in a row, and people sit down one at a time.

People are shy, so each one tries to sit as far as possible from the people already seated. Specifically, a seat can be chosen according to the rules below.

If no one is seated yet, a person can sit in any seat.
If someone is already seated and there is a seat with no one in the adjacent seats, a person can sit in the one of those seats whose distance to the nearest seated person is the largest.
If someone is already seated and no seat has empty adjacent seats, no one else can sit down.

These people are shy, but they are also kind people who pursue the public good. So among the seating arrangements that satisfy these conditions, they choose the one in which the most people end up seated.

Given the number of seats $N$ , find the maximum number of people who can be seated.

Input

The first line contains the number of seats $N$ . ( $1 \leq N \leq 3\,000\,000$ )

Output

On the first line, print the maximum number of people who can be seated.

Examples5

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