Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

#### PrefixSuffixSet

Calculate the number of pairs (P, S) such that {A, ..., A[P]} = {A[S], ..., A[N-1]}.

A non-empty array A consisting of N integers is given. A prefix suffix set is a pair of indices (P, S) such that 0 ≤ P, S < N and such that:

• every value that occurs in the sequence A, A, ..., A[P] also occurs in the sequence A[S], A[S + 1], ..., A[N − 1],
• every value that occurs in the sequence A[S], A[S + 1], ..., A[N − 1] also occurs in the sequence A, A, ..., A[P].

The goal is to calculate the number of prefix suffix sets in the array.

For example, consider array A such that:

A = 3 A = 5 A = 7 A = 3 A = 3 A = 5

There are exactly fourteen prefix suffix sets: (1, 4), (1, 3), (2, 2), (2, 1), (2, 0), (3, 2), (3, 1), (3, 0), (4, 2), (4, 1), (4, 0), (5, 2), (5, 1), (5, 0).

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the number of prefix suffix sets.

If the number of prefix suffix sets is greater than 1,000,000,000, the function should return 1,000,000,000.

For example, given:

A = 3 A = 5 A = 7 A = 3 A = 3 A = 5

the function should return 14, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..40,000];
• each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].