408707: GYM103269 D Tallest Dogpark

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

D. Tallest Dogparktime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

The City of Austin is building a new dogpark and would like to know your thoughts on its design. Knowing the local geography, you hope that you and your doggo can see over all the surrounding hills. Thus, you want to help the City build the tallest possible dogpark.

The City has set aside a $$$L$$$ length plot of land for the dogpark. Each of the $$$L$$$ locations in the dogpark will have some integer height $$$h_i$$$. To allow for easy entry, the park must begin and end with height $$$0$$$. To allow for optimal play, the heights of adjacent portions of the dogpark cannot differ by more than $$$1$$$.

Given the length $$$L$$$ of the dogpark, please provide the maximum possible height of the new dogpark.

Input

A single integer $$$1 \leq L \leq 10^5$$$, specifying the length of the dogpark.

Output

A single integer indicating the height of the tallest possible location within the dogpark.

ExamplesInput
4
Output
1
Input
5
Output
2
Note

For $$$L = 4$$$, we could have a dogpark of heights $$$0, 0, 1, 0$$$, so maximum height $$$= 1$$$.

For $$$L = 5$$$, we could have a dogpark of heights $$$0, 1, 2, 1, 0$$$, so maximum height $$$= 2$$$.

加入题单

上一题 下一题 算法标签: