// Arup Guha
// 10/2/2026
// Solution to COP 3503 Exam 1 Question 7

import java.util.*;

public class e1q7 {

	public static void main(String[] args) {
		Random r = new Random();
		
		// Some tests.
		for (int loop=0; loop<20; loop++) {
			
			// Do random array.
			int[] vals = new int[100];
			for (int i = 0; i<100; i++)
				vals[i] = r.nextInt(100) + 1;
			
			// Call both the easy slow method and the faster one.
			long correct = countTripsSlow(vals);
			long mine = countTriplets(vals);
			
			// Just see if they say the same thing.
			System.out.println(correct+" "+mine);
		}
	
	}
	
	// Solves the problem by just checking every possible triplet.
	public static long countTripsSlow(int[] a) {
		int n = a.length;
		long res = 0;
		for (int i=0; i<n; i++)
			for (int j=i+1; j<n; j++)
				for (int k=j+1; k<n; k++)
					if (a[i] < a[j] && a[j] < a[k])
						res++;
		return res;
	}
	
	// Solution for the test question
	public static long countTriplets(int[] a) {
		
		// Store the final answer here.
		long res = 0;
		
		// I use 3 bits.
		bit items = new bit(1000001);
		bit pairs = new bit(1000001);
		bit trips = new bit(1000001);
		
		// Just go through the array.
		for (int i=0; i<a.length; i++) {
			
			// Get # of items prior to this in the array that are lower than it.
			long cur = items.query(a[i]-1);
			
			// This is a bit for the items themselves.
			items.add(a[i], 1);
			
			// This is a bit for the number of increasing pairs that end here.
			pairs.add(a[i], cur);
			
			// This will tell us the number of triplets that end here as triplets just
			// build on pairs.
			long curT = pairs.query(a[i]-1);
			
			// Update our triplets.
			trips.add(a[i],curT);
			
			// Also add to the total all triplets that end at a[i].
			res += curT;
		}
	
		// Ta da!
		return res;
	}
}


class bit {

	private int n;
	private long[] arr;
	
	public bit(int myn) {
	
		// Get to a power of 2 > myn.
		n = 1;
		while (n < myn+5)
			n <<= 1;
			
		// Will store my bit sums.
		arr = new long[n];
	}
	
	public void add(int idx, long value) {
		
		// Add to positions in table that have idx as part of their responsibility.
		while (idx < n) {
			arr[idx] += value;
			idx += (idx & (-idx) );
		}
	}
	
	// Returns sum from index 1 to index idx.
	public long query(int idx) {
	
		// Add into sum all disjoint sets to cover range from index 1 to idx.
		long total = 0;
		while (idx > 0) {
			total += arr[idx];
			idx -= (idx & (-idx) );
		}
		
		return total;
	}
}