Horrible Truth

In the famous TV show "Find Out" there are n characters and a single Horrible Truth. To keep the series thrilling from beginning to end, the screenwriter decided that every episode must show exactly one important event.

There are three types of important events:

• a character A finds out the Truth;
• a character A finds out that another character B knows the Truth;
• a character A finds out that another character B does not know the Truth.

Initially nobody knows the Truth. Every event must be correct: every fact that is found out must actually be true at the moment it is found out. Once a character has found out a particular fact, she cannot find out that same fact again.

Moreover, to keep a sense of momentum, the writer never lets an episode show an important event of the same type as the immediately preceding episode.

Determine the maximal possible number of episodes the series can have.

The only line of input contains a single integer n — the number of characters in the show (1 ≤ n ≤ 100).

Print a single integer — the maximal possible number of episodes the series can have.