SOLVE

LATER

Monica and Gaming Obsession

Problem

Editorial

Analytics

Monica is a lagendary player of badminton. She is going to participate in a Knockout - Badminton tournament with n - 1 other players.

The organising committee are still deciding the order in which the games will happen and which team player is going to play with who. But they have already stated one rule:

Two player standoff if and only if the absolute difference of number of games played is atmost one.

So one thing is clear that both players had to attain victory in all of their matches in order to continue participating in the tournament.

Since the tournament has not started yet and Monica was being bored sitting and making faces she thought what will be the highest number of matches she will have to play if she is going to win the tournament. As you know Monica is poor in mathematics she asks for your help to solve the problem.(Of course she thinks you can do it !!)

**Input:**

The only line contains an integer n, the number of participants in badminton tournament.

**Output:**

Print the highest number of matches in which Monica (the final winner) can take part in.

**Contraints:**

$$ 2 \leq n \leq 10^{18} $$

**SAMPLE INPUT:**

Input

2

Output

1

Input

3

Output

2

Input

4

Output

2

Input

10

Output

4

**EXPLAINATION:**

NOTE: In all samples we consider that player number 1 is the Monica.

In the first sample, there would be only one game so the answer is 1.

In the second sample, player 1 can consequently beat players 2 and 3.

In the third sample, player 1 can't play with each other player as after he plays with players 2 and 3 he can't play
against player 4, as he has 0 games played, while player 1 already played 2. Thus, the answer is 2 and to achieve
we make pairs (1,2) and (3,4) and then clash the winners.

Figure out the fourth sample yourself. :P

Problem Setter - Priyanshu Kumar

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Marking Scheme:
Marks are awarded when all the testcases pass.

Allowed Languages:
C,
C++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala 2.11.8,
Swift,
Visual Basic

Initializing Code Editor...

{"1bb53e1": "/pagelets/recommended-problems/algorithm/monica-and-gaming-obsession-2/", "1bb53a0": "/pagelets/suggested-problems/algorithm/monica-and-gaming-obsession-2/", "1bb53b7": "/pagelets/problem-author-tester/algorithm/monica-and-gaming-obsession-2/", "1bb53cc": "/pagelets/problems-hint/algorithm/monica-and-gaming-obsession-2/", "1bb5381": "/pagelets/show-submission/algorithm/monica-and-gaming-obsession-2/"}

{}

realtime.hackerearth.com

80

85906240404005bba793f67ee85e3f646106fd68

58a29e5cae2309f04b28

/realtime/pusher/auth/