Sum of unique elements in all sub-arrays of an array Given an array $A$, sum the number of unique elements for each sub-array of $A$.  If $A = \{1, 2, 1, 3\}$ the desired sum is $18$.

Subarrays:

{1} - 1 unique element
{2} - 1
{1} - 1
{3} - 1
{1, 2} - 2
{2, 1} - 2
{1, 3} - 2
{1, 2, 1} - 2
{2, 1, 3} - 3
{1, 2, 1, 3} - 3


I have a working solution which sums the unique elements for all sub-arrays starting at index $0$, then repeats that process at index $1$, etc. I have noticed that for an array of size $n$ consisting of only unique elements, the sum I desire can be found by summing $i(i + 1) / 2$ from $i = 1$ to $n$, but I haven't been able to extend that to cases where there are non-unique elements.  I thought I could use that fact on each sub-array, but my control logic becomes unwieldy.  I've spent considerable time trying to devise a solution better than $O(n^2)$ to no avail.  Is there one?

Secondary question:  if there is no better solution, are there any general guidelines or hints to recognize that fact?
Hint: Use an extra $O(n)$-spaced array of pointer to the last (biggest) index of each distinct value. Then, this array is very helpful when you do your above algorithm.

Lastly, we should have an $O(n)$ algorithm.