\(N\) саннан тұратын \(a\) массиві бар. \(a_i = a_k\) және \(a_i < a_j\) болатын (\(i < j < k\)) үштіктер санын табыңыз.

Енгізу

Бірінші жолда \(N\)(\(1 \le N \le 300000\)).

Екінші жолда \(N\) бүтін сан \(a_1, a_2, \cdots, a_N\)(\(1 \le a_i \le N\)).

Шығару

Есептің жауабын шығарыңыз.

Бағалау жүйесі

Мысалдар

Енгізу 1

6
2 3 2 1 3 2

Жауап 1

4

Енгізу 2

10
1 2 1 2 3 1 2 1 3 1

Жауап 2

28

Ескертпелер

Бірінші мысалды келесі \((i,j,k)\) үштіктері есеп шартына келеді: (\(1,2,3\)), (\(1,2,6\)), (\(1,5,6\)) және (\(3,5,6\)).