1. You are given an integer N, which represents the length of a rod, and an array of integers, which represents the prices of rod pieces of length varying from 1 to
N.
2. You have to find the maximum value that can be obtained by selling the rod.
3. You can sell it in pieces or as a whole.Input Format
A number N arr1 arr2.. N integers
Output Format
Check the sample output and question video.
Constraints
1 <= N <= 100000 1 <= arr[i] <= 10^8
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
8 1 5 8 9 10 17 17 20
Output
22