Notes

The main point of this problem is that number of lucky numbers in array is  ≤ 1000. Imagine that there is array of 1000 number in range [1;1000] each, and you want to find number of such pairs that there is no equal number in both segments. How to solve this problem? Let we have fixed left point of right segment, let it be i. The you should iterate through all j (i ≤ j) - right point of right segment. If you have some fixed right segment [i;j], then there is some set S of numbers that are in that right segment. So, segment [0;i - 1] will be divided in some subsegments that don't contain any number from S. For example, let S = {1, 2, 3} and segment [0;i - 1] is [2, 4, 2, 3, 6, 5, 7, 1], then there will be such subsegments (0-based numeration): [1;1], [4;6]. Of course, any subsegment of that subsegments will be good too: they dont contain any number from S, too. So, you can keep in set (or some structure like set) all good subsegments and keep number of all good subsegments in [0;i - 1]. When you iterate j from i to n - 1, you will add some numbers to S. When you add some number in S, you should add all occurrences of that number in subarray [0;i]. Notice, that when some number is already in S, you don't need to look at that numbers. So, for fixed i you should do O(n * logn) operations - any number from a[0;i - 1] will be added at most once to set.

Now, we have not only lucky numbers. So, the problem is the same, but between number there are some "bad" numbers - in this case this are unlucky numbers. But, you can notice, that if we will fix only such i that a[i] is lucky and iterate j only such that a[j] is lucky then you can calculate result in the same way that in simpler problem. But that method allow you to only count such pairs that right one contains some lucky number. So you also need to count other ones. To do so you can fix some i - left point of right segment, such that a[i] is unlucky. Let F(i) equals to minimum such j (j > i) that a[i] is lucky. Then there are F(i) - i ways to expand right segment. All such right segments doesn't contain any lucky number. So any left segment will be good. And there are i * (i + 1) / 2 of such left segments (0-based).

http://codeforces.com/blog/entry/3746