Loại xúc xắc phổ biến nhất có \(6\) mặt, mỗi mặt ghi một số nguyên khác nhau từ \(1\) đến \(6\), nhưng nhiều trò chơi dùng các loại khác. Cụ thể, \(dk\) là một xúc xắc có \(k\) mặt, mỗi mặt ghi một số nguyên khác nhau từ \(1\) đến \(k\). Một \(d6\) là xúc xắc thông thường, \(d4\) có bốn mặt, còn \(d1000000\) có một triệu mặt.

Trong bài này, ta bắt đầu với một bộ sưu tập \(N\) xúc xắc. Xúc xắc thứ \(i\) là một \(dS_i\), nghĩa là nó có \(S_i\) mặt mang các số nguyên từ \(1\) đến \(S_i\). Một dãy liên tiếp độ dài \(\ell\) bắt đầu tại \(x\) là danh sách \(x,x+1,\ldots,x+(\ell-1)\). Ta muốn chọn một số xúc xắc, có thể là tất cả, và chọn một số trên mỗi xúc xắc để tạo thành một dãy liên tiếp. Dãy dài nhất có thể tạo theo cách này là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Sau đó là \(T\) bộ test. Mỗi bộ test được mô tả bằng hai dòng. Dòng đầu chứa số nguyên \(N\), số xúc xắc trong trò chơi. Dòng thứ hai chứa \(N\) số nguyên \(S_1,S_2,\ldots,S_N\), mỗi số là số mặt của một xúc xắc khác nhau.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), và \(y\) là số xúc xắc đầu vào lớn nhất có thể được đưa vào một dãy liên tiếp.

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1\le N\le10\) và \(4\le S_i\le20\) với mọi \(i\).
• Test Set 2 (phán quyết hiển thị): \(1\le N\le10^5\) và \(4\le S_i\le10^6\) với mọi \(i\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
4
6 10 12 8
6
5 4 5 4 4 4
10
10 10 7 6 7 4 4 5 7 4
1
10

Case #1: 4
Case #2: 5
Case #3: 9
Case #4: 1

Nguồn

Google Code Jam 2022, Vòng loại, bài d1000000.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.