All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Number Sum
/

Algorithms, Brute-force search, Dynamic Programming, Implementation

Problem
Editorial
Analytics

Alice is given an array of $$N$$ integers. Now, she is playing a game with Bob. In one turn Alice picks a sub-array of the given array $$A$$. In every turn, she picks a new subarray i.e. one with either different starting index or different ending index from the subarrays picked before.

Now, Bob starts shouting the natural numbers from beginning i.e. he first says $$1$$ then $$2$$ and so on. Alice stops him at the first integer which does not appear in the subarray that she has picked in this turn. Later on, she asks Bob to write the sum of all the values in which she stops him on a paper. Bob is weak in maths, can you help him?

Note: Please go through the sample carefully.

Input Format

The first line contains a single integer $$N$$. The next line contains $$N$$ space-separated integers, where the $$i$$-th integer denotes $$ A[i] $$.

Output Format

Print the single integer representing the required result.

Constraints

$$ 1 \le N \le 5 000 $$
$$ 1 \le A[i] \le 10^9 $$

SAMPLE INPUT
3
1 2 3
SAMPLE OUTPUT
12
Explanation

Since, Alice can pick any subarray in any order. So let's find out the answer for each subarray and then add it.

Array = $$[1\;2\;3]$$

In the below lines $$[a , b]$$ denotes the subarray that inclues all elements in the range $$[a , b]$$:

$$[1 , 1] = 2$$
$$[1 , 2] = 3$$
$$[1 , 3] = 4$$
$$[2 , 2] = 1$$
$$[2 , 3] = 1$$
$$[3 , 3] = 1$$

So, the answer is $$2 + 3 + 4 + 1 + 1 + 1 = 12$$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?