打家劫舍

题目描述

你是一个专业的小偷，计划偷窃一条街上的房屋。每间房内都藏有一定现金，但相邻的两间房屋不能同时被偷（会触发警报），而且每间房有防盗等级，如果偷了某间房，它的邻居的防盗等级会提高，导致下次偷邻居时收益减少一半。

具体规则：

• 房屋 i 有基础金额 a[i]
• 如果房屋 i 被偷，且房屋 i-1 也被偷，则房屋 i 的实际收益为 a[i] / 2
• 如果房屋 i 被偷，且房屋 i+1 也被偷，则房屋 i 的实际收益为 a[i] / 2
• 如果两边都被偷，收益为 a[i] / 3
• 否则收益为 a[i]

求能获得的最大总收益。

输入格式

第一行：N 第二行：a[1..N]

输出格式

最大总收益（整数，向下取整）

数据范围

1 ≤ N ≤ 10^5，1 ≤ a[i] ≤ 10^9

样例

输入：

5
8 5 9 6 7

输出：

24

解释：偷1、3、5号，收益8+9+7=24