All submissions for this problem are available.
Leonardo Da Vinci is shopping for his friend's birthday. The shop has N gifts placed in a row and numbered from 1 to N from left to right. The price of the ith gift is Pi. Leonardo wants to buy atmost two gifts for his friend such that the total price is maximum. Note that he has to buy at least one gift for his friend.
Also, the gifts he buys should not be similar. Two gifts are similar if they are placed next to each other in the shop. For example, the ith gift is similar to (i − 1)th and (i + 1)th gift.
The first line of input contains a single integer N the number of gifts available in the shop. The next line contains N space-seperated integers denoting Pi.
Print one integer denoting the answer to the problem.
- 1 ≤ N ≤ 100000
- -109 ≤ Pi ≤ 109
3 1 2 3
Leonardo can buy the gifts 1 and 2. The total price will be 4. This is the maximum possible. (Note that he cannot buy the gifts 2 and 3 because they are similar.)
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions