Hello everyone, I have a very hard problem (in my opinion) in my country's contest. I need your help, thanks a lot

Given an array a with N (1 <= N <= 200000) elements (1 <= a[i] <= N). Count how many triples (i, j, k) with satisfies:

. 1 <= i < j < k <= N . for each value x in subarray [ i .. j ], x is appears in subarray [ j + 1 .. k ] and for each value y in subarray [ j + 1 .. k], y is appears in subarray [i .. j]

For an example

N = 7

a = [3 1 2 1 2 3 1]

Output is 4

There are 4 triples (i, j, k): (1, 3, 6), (1, 3, 7), (1, 4, 7), (2, 3, 5)