← 返回题目列表

Codeforces · 2226/A

A. 令人不安的分布

中文机器翻译题面 查看原题

给你一个数组 $$$[a_1, a_2, \ldots, a_n]$$$。您希望通过执行任意多次以下操作来使数组为空:

  • 选择任意索引序列 $$$1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le |a|$$$ (注意 $$$|a|$$$ 表示数组 $$$a$$$ 的当前长度),使得 $$a_{i_1} \le a_{i_2} \le \ldots \le a_{i_k}$$
  • 从数组 $$$a$$$ 中删除元素 $$$a_{i_1}, a_{i_2}, \ldots, a_{i_k}$$$。
  • 此操作产生的成本等于 $$$a_{i_1} \times a_{i_2} \times \cdots \times a_{i_k}$$$。

确定 最小值 从数组 $$$a$$$ 中删除所有元素所需的总成本。请注意,总成本等于执行的所有操作所产生的成本总和。

由于答案可能非常大,请以 $$$676\,767\,677$$$ 为模报告答案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — 数组的元素。

输出

对于每个测试用例,输出一个整数 - 使数组 $$$a$$$ 为空所需的最小总成本。

由于答案可能很大,因此输出对 $$$676\,767\,677$$$ 取模的答案。

示例

输入
复制

3
5
1 2 1 2 3
3
3 2 1
4
1 1 1 1

输出
复制

7
6
1

注意

对于第一个测试用例,

  • 操作 1:选择 $$$i_1 = 1$$$、$$$i_2 = 2$$$ 和 $$$i_3 = 4$$$。这会产生 $$$1 \cdot 2 \cdot 2 = 4$$$ 的成本。删除这些索引处的元素后,数组变为 $$$a = [1, 3]$$$。

  • 操作2:选择 $$$i_1 = 1$$$ 和 $$$i_2 = 2$$$。这会产生 $$$1 \cdot 3 = 3$$$ 的成本。删除这些索引处的元素后,数组将变为空。

因此,总成本等于 $$$4 + 3 = 7$$$。可以证明这是最小可能的总成本。