408714: GYM103270 D Tallest Dogpark

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.

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

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

4

1

5

2

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$$$.