T1 mspaint

题目描述

你找到一款抽象游戏：2D-MC。

你随了一个世界，想在这个世界上玩建筑，但是地不平整，你需要把地弄平。

具体地，你有一个长为 $n$ 个格子的地面，第 $i$ 个格子的初始海拔高度为 $s_i$，保证 $s_i\in[1,n]\cap\mathbb{N}$。

你每次可以进行以下两种操作之一：

• 花费 $1$ 金钱，移除现有的魔法阵并在选定区间 $[l,r]$ 布置新的魔法阵。为了保证魔法阵正常生效，你需要保证这段区间的海拔相同。
• 令魔法阵所属区间的海拔高度为 $x$。你可以选择一个整数 $y\in[1,n]\cap\mathbb{N}$，花费 $x\times(x\operatorname{xor}y)$ 点魔力，将魔法阵所在区间的海拔高度重置为 $y$。

你需要在最小化金钱花费的前提下最小化魔力花费，使得所有格子的海拔高度均相等。

输入格式

第一行一个数 $n$。

第二行 $n$ 个整数，表示序列 $s$。

输出格式

一行两个整数，表示你的金钱花费和魔力花费。

评分方式

对于一个测试点：

• 如果你的输出格式不正确（不为两个非负整数），你将获得 $0$ 分；
• 如果你正确回答了该测试点的金钱花费，但没有正确回答魔力花费，你将得到这个测试点 $50\%$ 的分数；
• 如果你的答案完全正确，你将得到这个测试点 $100\%$ 的分数。

样例

样例输入 #1

4
1 2 3 1

样例输出 #1

2 8

样例输入 #2

10
6 2 10 1 8 5 4 10 3 7

样例输出 #2

8 143

样例 $3$

见附件中的 ex_mspaint3.in 与 ex_mspaint3.ans。

该样例满足子任务 $3$ 的约束。

数据范围

对于 $100\%$ 的数据， $1\leq n\leq500$，$1\leq s_i\leq n$。