括号

给定一个整数 n。生成所有长度为 n 的合法括号序列，并按字典序升序输出。合法括号序列定义：

（1）空字符串是合法的；

（2）若字符串 s 合法，则 (+s+) 合法；

（3）若字符串 s 和 t 合法，则 s+t 合法。

时间限制：1000ms内存限制：256MB

输入格式

输入一个整数n。

输出格式

每行输出一个合法括号序列（按字典序升序）。若无解则不输出。

输入样例#1

2

输出样例#1

()

输入样例#2

4

输出样例#2

(())
()()

输入样例#3

6

输出样例#3

((()))
(()())
(())()
()(())
()()()

数据范围：

1≤N≤20，N 是偶数。

金字塔

给定长度为 n 的字符串 s。从 s 中提取子序列，组成 pyramid 字符串的方法有多少种？答案需对 109+7取模后输出。

时间限制：1000ms内存限制：256MB

输入格式

第一行：一个整数 n;

第二行：一个字符串 s。

输出格式

输出组成 pyramid 的方法数（取模 109+7）。

输入样例#1

5
pxxxx

输出样例#1

0

输入样例#2

10
pyyradmiid

输出样例#2

4

数据范围：

1≤N≤105，s 仅包含小写英文字母。

古董

拍卖师准备了 N 件古董进行拍卖。这些古董有以下重要特性：

陈列规则：所有古董按 1、……、N 编号陈列在一条长廊中，每天拍卖师只能从长廊任一端取出一件古董拍卖。

升值效应：古董拍卖顺序直接影响成交价。若第 i 件古董在第 a天拍卖，成交价为 Vi×a（Vi 为初始估价）。

价值分布：第 i 件古董的初始估价 Vi 取决于其陈列位置——从入口端开始，第 i 个展柜内的古董估价为Vi。

拍卖师需要制定最优拍卖顺序，最大化总成交额。请帮助他计算出古董全部售出后的最大收益。

时间限制：1000ms内存限制：256MB

输入格式

第一行：古董数量 N；

接下来 n 行：古董初始估价序列 V1～VN；

输出格式

一行整数，表示最大总收益。

输入样例

5
1
3
1
5
2

输出样例

43

数据范围：

1≤N≤2000，1≤Vi≤1000。

搬运水果

在果园里，n 堆果实排成一个环形，第 i 堆果实的重量为 ai。果农需要将所有果实合并成一堆。合并规则如下：

（1）每次只能合并相邻的两堆，新堆的重量为两堆重量之和；

（2）每次合并消耗的体力等于新堆的重量；

（3）合并后新堆与剩余堆仍保持环形排列。

请设计合并顺序，求出合并全过程消耗的最小总体力与最大总体力。

时间限制：1000ms内存限制：256MB

输入格式

第一行：整数 n，表示果实堆数；

第二行：n 个整数 a1、a2、……、an，表示每堆果实的重量。

输出格式

第一行：最小总体力消耗；

第二行：最大总体力消耗。

输入样例

4
4 5 9 4

输出样例

43
54

数据范围：

1≤n≤100，1≤ai≤1000。