House Robbery :
Difficulty Level : Easy
Submissions : 736
Asked In :
Marks :10
: 11 | : 1
There are $$$N$$$ houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value of these houses, but he can't steal in two adjacent houses because the owner of the stolen houses will tell his two neighbors left and right sides. The task is to find what is the maximum stolen value.
Input
The first line contains an integer $$$N$$$. The second line contains $$$N$$$ integers $$$Arr_{i}$$$ denoting the value of houses.$$$(1 \le N \le 10^5)$$$$$$(1 \le Arr_{i} \le 10^4).$$$
Output
Output maximum stolen value.
Examples
Input
3 1 2 3
Output
4
Input
4 5 6 3 10
Output
16
Input
1 9139
Output
9139
