Non-Crossing Cow Crosswalks

Farmer John has N breeds of cows, numbered from \(1\) to \(N\). Each breed occupies exactly one pasture on both sides of a long road. A pair of cow breeds \(a\) and \(b\) get along if and only if \(|a-b| \le 4\). Farmer John wants to draw as many crosswalks as possible on the road. Each crosswalk must satisfy the following conditions:

• It connects a pasture from the left side of the road to a pasture on the right side.
• The two pastures it connects must contain cow breeds that get along (i.e. if the breeds are \(a\) and \(b\), then \(|a-b| \le 4\)).
• Crosswalks cannot intersect in the middle of the road.
• Each pasture can be connected to at most one crosswalk.

Determine the maximum number of crosswalks that Farmer John can draw.

Note: Since the left and right pastures are arranged in order of the cow breeds (from \(1\) to \(N\)), a natural pairing exists between pasture \(i\) on the left and pasture \(i\) on the right (because \(|i-i| = 0 \le 4\)). As such, an optimal solution is always to pair each pasture with its corresponding one. Therefore, the answer is \(N\).

inputFormat

The input consists of a single integer \(N\) (\(1 \leq N \leq 10^5\)), representing the number of cow breeds and pastures on each side.

outputFormat

Output a single integer, the maximum number of crosswalks that can be drawn.

sample

1

1