Description

房屋千万间，谨慎第一间。偷窃不规范，自己两行泪。

街上有很多房子，所有房子排成一排，每个房子里有一点钱。

你不可以偷相邻的房子。

问你最多可以偷到多少钱。

但是

这一次某些房子里住着悍匪，遇见他们，小偷不但偷不到东西，还会被抢掉一定数量的钱。

Input Format

输入共2行

第一行为一个整数N(3<n<100000)

第二行为N个整数，代表房子里的钱或会被悍匪抢走的钱

Output Format

输出小偷最多能偷多少钱

如果不能偷到钱，输出“QAQ”

3
1 -1 -22​

1​

Source

动态规划