Bánh kếp thường được phục vụ theo chồng, nhưng Infinite House of Pancakes luôn đón nhận thay đổi! Điểm quảng cáo mới của nhà hàng là phục vụ bánh kếp từ một deque, tức hàng đợi hai đầu.

Bạn là nhân viên phục vụ của nhà hàng và nhiệm vụ là phục vụ mọi chiếc bánh trong deque. Khách đến lần lượt từng người và mỗi người nhận một chiếc bánh. Với mỗi khách, bạn phải phục vụ chiếc bánh ngoài cùng bên trái hoặc ngoài cùng bên phải của deque; quyền lựa chọn thuộc về bạn. Khi được phục vụ, chiếc bánh biến mất khỏi deque, để lộ chiếc nằm cạnh nó. Khi chỉ còn một chiếc, lựa chọn duy nhất là phục vụ chiếc ấy, rồi công việc hoàn tất.

Mỗi chiếc bánh có một độ ngon. Vì khách hàng không được chọn bánh, một khách chỉ phải trả tiền nếu chiếc bánh họ nhận ngon ít nhất bằng từng chiếc mà tất cả khách trước đó đã nhận. Khách đầu tiên luôn trả tiền vì chưa có khách nào trước đó.

Nếu phục vụ bánh theo thứ tự làm số người trả tiền lớn nhất, có bao nhiêu khách sẽ trả tiền?

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(\mathbf{T}\). Tiếp theo là \(\mathbf{T}\) bộ test, mỗi bộ được mô tả bằng hai dòng.

Dòng đầu của một bộ test chứa số nguyên \(\mathbf{N}\), là số bánh trong deque. Dòng thứ hai chứa \(\mathbf{N}\) số nguyên \(\mathbf{D}_1,\mathbf{D}_2,\ldots,\mathbf{D}_\mathbf{N}\), trong đó \(\mathbf{D}_i\) là độ ngon của chiếc bánh thứ \(i\) tính từ trái sang trong deque.

Dữ liệu ra

Với mỗi bộ test, in một dòng theo định dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là số khách trả tiền khi bạn phục vụ bánh theo một thứ tự tối đa hóa số lượng ấy.

Ràng buộc

• \(1\le\mathbf{T}\le100\).
• \(1\le\mathbf{D}_i\le10^6\) với mọi \(i\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(2\le\mathbf{N}\le20\).
• Test Set 2 (phán quyết hiển thị): \(2\le\mathbf{N}\le100\).
• Test Set 3 (phán quyết ẩn): \(2\le\mathbf{N}\le10^5\).

Đ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
2
1 5
4
1 4 2 3
5
10 10 10 10 10
4
7 1 3 1000000

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

Nguồn

Google Code Jam 2022, Vòng 1B, bài Pancake Deque.

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