今晚是大脑晚餐之夜,所有僵尸将聚集在一起狼吞虎咽一些美味的大脑。狡猾的海蒂计划伪装成其中一员,隐姓埋名地破坏聚会。她的目标是至少带走一个大脑,这样她就可以分析家乡僵尸的心态并获得战略优势。
今晚他们将是 N 位客人:N - 1 个真正的僵尸和一个假僵尸,我们的海蒂。活死人的等级制度就像他们爱大脑一样:每个人都有一个从 1 到 N - 1 范围内的独特等级,而看起来与其他人略有不同的海蒂被归为最高等级 N。今晚将展示一个装有大脑的箱子,每个参与者都会看到有多少个。然后,这些将根据以下程序在与会者之间分配:
最高等级的僵尸会建议谁获得多少个大脑(每个大脑都是一个不可分割的实体)。随后进行投票。如果至少有一半的与会者接受了这个提议,那么大脑就会按照建议的方式分享,盛宴就开始了。但如果没有达到多数,那么排名最高的僵尸就会被杀死,等级中的下一个僵尸必须提出建议。如果他也被杀了,那么排名第三的僵尸也得一票,以此类推。(只要有一半的选票就足够了——如果平局,排名最高的活僵尸的票算两次,他当然会投票赞成自己的建议,以求活下去。)
你应该知道,僵尸非常贪婪和狡猾,他们也知道这一点——基本上所有僵尸的大脑都是相似的。因此,僵尸永远不会接受对他来说次优的报价。也就是说,如果一个提议并不严格优于后来的潜在提议,他就会投票反对。别搞错了:虽然僵尸通常看起来相当迟钝,但今晚他们的智力却是完美的。每个僵尸今晚的优先事项按降序排列是:
1. 在事件中幸存下来(他们已经经历过一次死亡并且知道这并不好玩),
2. 获得尽可能多的大脑。
海蒂先走,必须提出至少一半与会者接受的提议,并为海蒂自己分配至少一个大脑。
胸部中最少需要多少个大脑才能实现这一点?
输入
输入的唯一一行包含一个整数:N,与会者人数 (1 ≤ N ≤ 109)。
输出
输出一个整数:箱子里最少有多少个大脑,海蒂可以带一个大脑回家。
示例
输入 #1
1
输出 #1
1
输入 #2
4
输出 #2
2