Problem Description

After finishing the task assignment, West 314 arrived at the west of the ancient city of Loulan. It is said that long ago (even earlier than the ancient city of Loulan) there were two tribes living on this land. One tribe worshiped the dagger (V), and the other tribe worshiped the shovel (∧). They used the shapes V and ∧ to represent their own tribal totems.

West 314 discovered a huge mural under the ancient city of Loulan. The mural is marked with $n$ points. After measurement, it was found that the horizontal positions and vertical positions of these $n$ points are pairwise different. West 314 believes that the information contained in this mural is related to the relative positions of these $n$ points, so we may assume the coordinates are $(1,y_1),(2,y_2),\cdots,(n,y_n)$, where $y_1\sim y_n$ is a permutation of $1$ to $n$.

As shown in the figure, $y_1=1$, $y_2=5$, $y_3=3$, $y_4=2$, $y_5=4$.

West 314 plans to study how many totems are contained in this mural. The definition of a V totem is as follows (note: the totem’s shape only depends on the relative order of the three $y$-coordinates): $1\le i<j<k\le n$ and $y_i>y_j$, $y_j<y_k$.

The totem of the tribe that worships ∧ is defined as: $1\le i<j<k\le n$ and $y_i<y_j$, $y_j>y_k$.

West 314 wants to know the number of totems of the two tribes among these $n$ points. Therefore, you need to write a program to compute the number of V and the number of ∧.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ positive integers, representing $y_1,y_2,\cdots,y_n$.

Output Format

Output two numbers separated by a space, in order: the number of V and the number of ∧.

5
1 5 3 2 4

3 4

Hint

Constraints

• For $10\%$ of the testdata, $n\le 600$.
• For $40\%$ of the testdata, $n\le 5000$.
• For $100\%$ of the testdata, $n\le 200000$, and the answer does not exceed $2^{63} - 1$.

Translated by ChatGPT 5