I. Itwise Bor
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

João is visiting a planet far from Earth, the alien planet PEI-X40, governed by Nei, a peaceful leader who warmly welcomed João's arrival.

The inhabitants of this planet use binary representation to express numbers: for example, the number $$$6$$$ on Earth is represented as "$$$110$$$" there. In this representation, they refer to each digit as an "it", upon which they define operations called "itwise". Among these, the main ones are "band" and "bor".

The bor operation is particularly interesting to an astronomer like João because Nei has decreed that the beauty of a constellation is defined as the itwise bor of the brightness values of all the stars within it.

Curious, João studied a bit about bor and learned that it is represented by the symbol "$$$|$$$" and works as follows:

For each position $$$i$$$ in the binary representation of $$$X$$$ and $$$Y$$$, if $$$X$$$ has the $$$i$$$-th it equal to $$$1$$$ and/or $$$Y$$$ has the $$$i$$$-th it equal to $$$1$$$, then $$$X$$$ $$$|$$$ $$$Y$$$ has the $$$i$$$-th it equal to $$$1$$$. Otherwise, $$$X$$$ $$$|$$$ $$$Y$$$ has the $$$i$$$-th it equal to $$$0$$$.

For example, in binary, $$$101$$$ $$$|$$$ $$$010 = 111$$$. This is equivalent to $$$5$$$ $$$|$$$ $$$2 = 7$$$ in the Earth decimal system.

While gazing at the sky of PEI-X40, João noticed a peculiar constellation: there were $$$N$$$ stars in the sky, one next to the other. He then recorded the brightness of each star $$$b_1, b_2, \cdots, b_N$$$, in the order they appeared.

After jotting down some mathematical expressions, he realized that this constellation can be divided into several continuous constellations in such a way that the structure of the stars being next to each other is preserved.

Now, João wants to divide the constellation into several others so that the sum of the beauties of all these constellations is maximized, and, among all the ways that yield the maximum sum, he wants the division with the smallest number of constellations. Since the inhabitants of PEI-X40 didn't train him well enough for this, he asked for your help.

Input

The input consists of two lines.

The first line contains an integer $$$N$$$ $$$(1 \le N \le 3 \cdot 10^5)$$$, the number of stars in the original constellation.

The next line contains $$$N$$$ integers $$$b_1, b_2, \cdots, b_N$$$ $$$(0 \le b_i \lt 2^{30})$$$, the brightness values of the stars in the order they appear in the sky.

Output

The output must contain two integers $$$S$$$ and $$$K$$$, the maximum possible sum of beauty and the minimal number of groups required to achieve this sum, respectively.

Examples
Input
5
4 1 2 1 3
Output
11 3
Input
3
1 2 3
Output
6 2
Input
4
7 7 7 7
Output
28 4
Input
5
1 3 4 8 2
Output
18 3
Note

In the first example, João can divide the constellation into three groups: $$$[4,1]$$$, $$$[2,1]$$$, and $$$[3]$$$ to obtain the maximum sum of $$$5 + 3 + 3 = 11$$$.

In the second example, João can divide the constellation into two groups: $$$[1,2]$$$ and $$$[3]$$$ to obtain the maximum sum of $$$3 + 3 = 6$$$.