No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

Consider a necklace made of 2N-1 black and white beads, K of which are black. Necklace is called "beautiful" if it is possible to choose two black beads (not necessarily different) in such a way that one of two necklace parts strictly between them contains exactly N beads.

For example, if N=4 and K=3, necklace "WBWBWBW" is beautiful, and necklace "BBWWBWW" is not.

You need to find minimal K for which every necklace of 2N-1 beads is beatiful.

For example, if N=4 and K=3, necklace "WBWBWBW" is beautiful, and necklace "BBWWBWW" is not.

You need to find minimal K for which every necklace of 2N-1 beads is beatiful.

The first line of input contains odd integer number 2N-1 (5<=2N-1<=2^31-1).

Output minimal K for which every necklace of 2N-1 beads is beatiful.

Input

Test #1

5

Test #2

7

5

Test #2

7

Output

Test #1

3

Test #2

4

3

Test #2

4

Author: | Alexey Preobrajensky |

Resource: | Petrozavodsk Summer Training Sessions 2004 |

Date: | August 25, 2004 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2019 23:21:33 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|