URI Online Judge | 2526


By Ricardo Oliveira, UFPR BR Brazil

Timelimit: 1

The Federal University of Nlogônia (FUNl) has an University Restaurant (UR) that provides meals every day to all students in the university.

The restaurant’s menu is always composed by three distinct dishes: an entry, a side dish and a dessert. There are N dishes that can be used by the restaurant to make the menu. The dishes are very miscellaneous, such that any dish can be used as an entry, as a side dish or as a dessert.

However, the nutritionists demand the menu to be always well balanced. To that end, the entry must have less calories than the side dish, and the side dish must have less calories than the dessert. Also, the entry must have more fiber than the side dish, and the side dish must have more fiber than the dessert.

You task is to determine how many distinct menus can be made, i.e., in how many ways it is possible to select three dishes from the N available ones to make a valid menu.


The input contains several test cases. The first line of each test case contains the integer N (3 ≤ N ≤ 106). Consider that the dishes are numbered from 1 to N, in ascending order of their calories. Hence, you can consider that the i-th dish has i Calories.

The second line contains N distinct integers f1,f2,...,fN (1 ≤ fiN), indicating the amount of fiber in each dish. Dish i has fi units of fiber.

The input ends with end-of-file (EOF).


For each test case, print a line containing the number of menus that can be made.

Input Sample Output Sample

3 2 1
3 4 2 1
6 2 4 1 5 3