Neighborhood Theft (Circular)

Languages

An experienced robber is planning a heist on a circular street. Every house contains a certain amount of money, and all houses are arranged in a circle, meaning the first house is next to the last one. Additionally, adjacent houses have connected security systems that alert the police if two neighboring houses are robbed on the same night.

Given an array of integers numbers, where each element represents the amount of money in a house, return the maximum amount of money the robber can steal without triggering the alarm.

Input

  • numbers: number[]: An array of integers

Notes

  • The robber cannot steal from two adjacent houses

Examples

Input: numbers = [1,2,3,1]
Output: 4
Explanation: The robber can steal a maximum of 4 by robbing house at index 0 (value 1) and house at index 2 (value 3).
Input: numbers = [2,7,9,3,1]
Output: 11
Explanation: The robber can steal a maximum of 12 by robbing house at index 0 (value 2), house at index 2 (value 9).
Input: numbers = [3,6,1,0,6,0,0,9]
Output: 21
Explanation: The robber can steal a maximum of 21 by robbing house at index 1 (value 6), house at index 4 (value 6), house at index 7 (value 9).

Constraints

  • 1 <= numbers.length <= 100
  • 0 <= numbers[i] <= 400