A robber attempted to rob TS(Taka Sesh) Bank but failed to complete the task. However, he managed to open all the vaults successfully.
Bob is a scientist in a tech giant company specializing in developing AI-based robots. His work has earned him considerable fame in his field. Interestingly, Bob is also a client of TS Bank (Taka Sesh Bank), and like many others, he is also greedy for money. Taking advantage of the failed robbery, Bob decides to steal money from the vaults, sending an AI-based robot named ‘Alpha’ to TS bank to steal that money.
There are vaults arranged in a line left to right, where the vault has money in it.
There are two security guards, one of them guards the vault, and the other one guards the vault. The two guards have strict instructions not to leave their guarding posts.
Alpha can go only left or right. Alpha won’t visit a vault more than once. Whenever Alpha is in a vault, he will steal all the money in that vault.
Alpha starts stealing from the vault. Alpha is at a disadvantage that the vault is one of the vaults which are between the and the vault. Meaning Alpha has a guard in one of the vaults left of him and the other one guarding one of the vaults right of him, meaning .
Note that Alpha cannot steal from a guarded vault. So, Alpha stops stealing and escapes the bank if it encounters a guard.
Now you have to print what is the maximum amount of money Alpha can steal from the TS Bank.
The first line of input will contain four integers , separated by spaces — denoting the number of vaults and the positions of Alpha, the first security guard, and the second security guard, respectively.
The next line of input contains space separated integers , denoting that the vault has amount of money.
Output a single integer — denoting the maximum amount that Bob can steal from the bank.
Check out the samples for clarification.
Input | Output |
---|---|
5 3 1 5 9 2 1 5 3 | 6 |
Explanation: If Alpha moves to the left, it can steal from the and vaults, resulting in a total of . On the other hand, if it moves to the right, it can steal from the and vaults, resulting in a total of . Here, Alpha cannot steal from the vault because he has already visited vault, to steal from the vault he has to go through which he can’t. So, final value is . |