Dancing Tuples

Given an array AAA of size nnn, find how many tuple (i,j,k)(i, j, k)(i,j,k) are there such that 1≤i<j<k≤n1 ≤ i < j < k ≤ n1≤i<j<k≤n and Aj≤Ai≤AkA_j ≤ A_i ≤ A_kAj​≤Ai​≤Ak​.


This is a companion discussion topic for the original entry at https://toph.co/p/dancing-tuples