logo Algo Beat Contest
登录 注册

#10011. [Murasame's Contest 1] Color Merge

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Murasame

题目描述

给你一个包含 个整数的序列

你可以重复执行以下操作,直到序列中的所有元素都相同:

  • 从当前序列中选择两个相邻的元素
  • 如果 ,支付 的代价;否则支付零代价。
  • 改为 或将 改为 。你可以自由选择。

确定使所有元素变得相同时所需的最小总代价。

输入格式

第一行包含一个整数 ,表示测试用例的数量。

对于每个测试用例:

  • 第一行包含一个整数 ,表示序列的长度。
  • 第二行包含 个整数

输出格式

对于每个测试用例,输出一个整数,表示所需的最小总代价。

样例

输入

2
3
10 1 10
4
2 4 3 2

输出

10
14

输入

1
5
1000 1 1 1 1000

输出

2000

数据范围与提示

限制条件:

样例 1 测试用例 2 解释:

  • 选择 。代价:。将 改为 。序列变为:2 2 3 2。
  • 选择 。代价:。将 改为 。序列变为:2 2 2 2。
  • 总代价:

部分输入文件包含行末空格。请注意处理空白字符。