#BS0027. [HTOI-2] 猜球游戏
[HTOI-2] 猜球游戏
题目背景
公司的年终大会上,小B 为了收买人心 举行了一个猜球游戏。
题目描述
有 个杯子编号为 ,从左到右排成一行,所有的杯子都倒着扣在桌上。其中某些杯子底下藏有一个小球,如果小A能准确地猜出哪些杯子中藏了小球,小A就能获得奖品。
黑心商家小B规定,花费 元就能知道第 个杯子到第 个杯子之间(包括两端)球的数量是奇数还是偶数。
小A希望猜出每个杯子底下是否藏着小球。但是小A带的钱不多,他希望采用最佳询问策略,请你告诉小A他最少需要花多少钱?
输入格式
第一行一个正整数 。
第 行( )有 个整数,表示 。
输出格式
输出一个整数,表示最少花费。
样例 #1
样例输入 #1
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
样例输出 #1
7
提示
对于 的数据,。
对于 的数据,,。