提示: 欢迎访问OurACM平台。
Problem 1886 音乐

Accept: 237    Submit: 539
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

chjing电脑里有很多歌,每首歌由某个歌手唱的,梁静茹,林俊杰,周杰伦啊,比较多。每次听歌,chjing总是按照播放列表上的顺序,顺序的听下来。所以经常会连续的听到一个歌手唱的歌。老听到同一个人的歌不大好,于是,chjing决定计算一个列表上所有歌的fun值,并选取fun值总和最大的播放列表。

一首歌的fun值,是这样计算的,假设这首歌在位置i,由歌手t唱的,那么在大于i并且离i最近的位置j找到一首歌,也是t唱的,这首歌的fun值就是(j-i)。如果找不到,这首歌的fun值为0.一个播放列表的fun值,就是加上所有位置上的歌曲的fun值。

Input

第一行一个整数T,表示有T个测试用例。

以后每个用例一个整数n,表示有n首歌。(0 < n <= 22)

然后n个整数,第i个整数的值为s,代表第i首歌是s唱的。为方便起见,s是一个数字,代表某个歌手。0 <= s <= 15.

Output

打印“Case h:”,h是第h个用例。

然后下一行,输出所求的fun值。

每个样例后输出一行空行。

Sample Input

2 3 1 1 2 6 1 2 2 2 3 3

Sample Output

Case 1: 2 Case 2: 8

Hint

第一个样例: 排列顺序 1 2 1 Fun值:2+0+0=2; 第二个样例: 排列顺序: 3 2 1 2 3 2 Fun值:4+2+0+2+0+0=8

Source

chjing

Submit  Back  Status  Discuss