Longest Increasing and Descending Subsequences Game

Alice and Bob invented a new game. Given a sequence \(\{x_0,x_1,\ldots,x_{n-1}\}\), Alice gets a sequence \(\{a_0,a_1,\ldots,a_{n-1}\}\), where \(a_i\) is the length of the longest increasing subsequence (LIS) ending at \(x_i\). Bob gets a sequence \(\{b_0,b_1,\ldots,b_{n-1}\}\), where \(b_i\) is the length of the longest descending subsequence (LDS) starting at \(x_i\). The final score for Alice is the sum of the \(a_i\)'s, and the final score for Bob is the sum of the \(b_i\)'s.

Your task is to compute these two scores given the sequence \(\{x_0,x_1,\ldots,x_{n-1}\}\).

Note: In the context of this problem, an increasing subsequence is a sequence of indices \(i_1, i_2, \ldots, i_k\) such that \(i_1 < i_2 < \cdots < i_k\) and \(x_{i_1} < x_{i_2} < \cdots < x_{i_k}\). Similarly, a descending subsequence is one where for indices \(i_1, i_2, \ldots, i_k\) (with \(i_1 < i_2 < \cdots x_{i_2} > \cdots > x_{i_k}\).

inputFormat

The first line contains an integer \(n\) \((1 \le n \le 10^3)\) indicating the number of elements in the sequence.

The second line contains \(n\) space-separated integers \(x_0,x_1,\ldots,x_{n-1}\).

outputFormat

Output two integers separated by a space: the sum of \(a_i\) (Alice's score) and the sum of \(b_i\) (Bob's score).

sample

5
1 2 3 4 5

15 5