#1769. 珂朵莉的魔法步伐

珂朵莉的魔法步伐

珂朵莉的魔法步伐

题目背景

珂朵莉准备前往森林深处寻找一颗神奇的星光石。

她穿上了一双魔法鞋。每次发动魔法,鞋子都能让她移动一段距离。不过,魔法鞋有一个奇怪的特点:有时先走过头,再往回走,反而能更快抵达目的地。

珂朵莉想用尽可能少的魔法次数走到终点,于是把这个问题交给了你。

题目描述

珂朵莉起点位于数轴上的 00,目标是到达位置 nn。

每次发动魔法,她可以选择以下四种移动方式之一:

  • 向前移动 11 个单位。
  • 向后移动 11 个单位。
  • 向前移动 55 个单位。
  • 向后移动 55 个单位。

每种移动方式都恰好消耗一次魔法。允许经过终点以后再往回走,也允许经过负数位置。

请你计算,珂朵莉从 00 到达 nn 最少需要发动多少次魔法。

输入格式

一行一个整数 nn,表示目标位置。

输出格式

输出一行一个整数,表示最少需要发动的魔法次数。

样例 1

输入

4

输出

2

样例 2

输入

9

输出

3

样例解释

对于样例 1,可以先从 00 向前移动 55 个单位到达 55,再向后移动 11 个单位到达 44,共使用 22 次魔法。

对于样例 2,可以从 00 移动到 55,再移动到 1010,最后向后移动 11 个单位到达 99,共使用 33 次魔法。

数据范围

  • 1≤n≤1091 \le n \le 10^9。
  • nn 为整数。