{"code":"hist","name":"HIST","description":"Lỗ Ban là một vị thợ mộc nổi tiếng bậc nhất thời Tống của Trung Quốc với đôi bàn tay cực kỳ tài hoa\r\nkhéo léo. Ngưỡng mộ tài năng của Lỗ Ban, Vua Tống mời Lỗ Ban vào triều làm quan chuyên quản lý\r\nviệc thiết kế cung điện và chế tác vật dụng tinh xảo. Vua Tống trong một chuyến du ngoạn ở núi Ngũ\r\nNhạc tình cờ phát hiện một phiến đá ngũ sắc tuyệt đẹp, Vua Tống nảy ra ý định đem phiến đá này về\r\ncung để chế tác thành một bàn cờ. Nhưng Vua Tống nhanh chóng phát hiện ra rằng, phiến đá này có\r\nhình dạng kỳ lạ rất khó để có thể cắt ra phần diện tích vuông vắn đủ lớn cho bàn cờ. Vậy là Vua Tống\r\ntriệu Lỗ Ban vào triều để thương lượng:\r\nBề mặt phiến đá có thể được mô tả như là một hình đa giác được ghép thành từ nhiều phiến đá nhỏ\r\nhình chữ nhật có chung nhau một mép, có các chiều dài khác nay nhưng giống nhau về chiều rộng và\r\nbằng $1$ đơn vị. Trong hình vẽ dưới đây, phiến đá đa giác gồm các hình chữ nhật có chiều cao lần lượt từ\r\ntrái qua phải là $2,1,4,5,1,3,3$ và chiều rộng đều bằng $1$.k\r\n\r\nnote : đây có ảnh\r\n\r\n**Yêu cầu:** Bạn cần giúp Lỗ Ban tìm ra hình chữ nhật chung mép với các hình chữ nhật nhỏ và có diện\r\ntích lớn nhất nằm trong phiến đá đa giác nói trên. Ở hình vẽ dưới, hình chữ nhật lớn nhất là hình được\r\ngạch chéo.\r\n\r\n

Input

\r\n\r\n- Chứa một hoặc nhiều test. Mỗi test mô tả một đa giác bắt đầu bằng số nguyên $n (1 \\le n \\le 1000000)$ là\r\nsố lượng hình chữ nhật nhỏ cấu thành đa giác. Tiếp theo sau là n số nguyên $l_1, l_2, . . . , l_n$ với $0 \\le l_i \\le\r\n100000000$ lần lượt từ trái sang phải biểu thị chiều dài của các hình chữ nhật. Chiều rộng của các hình\r\nchữ nhật bằng nhau và bằng $1$. File kết thúc với dòng ghi duy nhất một số $0$.\r\n\r\n

Output

\r\n\r\n- Với mỗi test ghi trên một dòng diện tích của hình chữ nhật nằm trong đa giác thỏa mãn điều kiện đề\r\nbài.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 7 2 1 4 5 1 3 3\r\n 4 1000 1000 1000 1000\r\n 0\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 8\r\n 4000\r\n ```","points":100.0,"partial":true,"time_limit":1.0,"memory_limit":512000,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}