# Rod Cutting

easy

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.

## Constraints

1 <= N <= 100000 1 <= arr[i] <= 10^8

## Format

### Input

A number N arr1 arr2.. N integers

### Output

Check the sample output and question video.

## Example

Sample Input

8
1
5
8
9
10
17
17
20

### Sample Output

22

Question Video