Boss Battle

Time limit2sMemory limit512 MB

Summary

Find the minimum number of bombs needed to guarantee hitting a boss hiding behind one of n circular pillars, where each bomb hits three adjacent pillars and the boss may shift one step after each miss.

Level: Medium7 of 10
Topics: Greedy, Math, Game theory
Solved: No attempts yet

Problem

You are stuck on the boss level of your favourite video game. The boss battle takes place in a circular room with $n$ indestructible pillars spaced evenly around the wall. The boss hides behind one of the pillars, and you do not know which one. After that, you and the boss act in turns.

On your turn you can throw a bomb past a pillar of your choice. The bomb defeats the boss if the boss is behind that pillar, or behind either of the two pillars next to it.

If the boss was not defeated, it takes its turn. It can stay where it is, or it can move to a pillar next to its current one. The smoke of the explosion hides this move from you.

Last time you failed because you ran out of bombs. This time you want to carry enough bombs that you defeat the boss whatever it does. Find the smallest number of bombs that is enough in the worst case.

The picture below shows the case $n = 4$ , where 2 bombs are enough. Grey pillars are pillars the boss cannot be hiding behind, and the black circle is the bomb.

Input

The input is one line with a single integer $n$ ( $1 \le n \le 100$ ), the number of pillars in the room.

Output

Print the minimum number of bombs needed to defeat the boss in the worst case.

Examples2

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