KAGAIN - Chiến trường Ô qua

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Lại nói về Lục Vân Tiên , sau khi vượt qua vòng loại để trở thành Tráng Sỹ , anh đã gặp được Đôrêmon và được chú mèo máy cho đi quá giang về thế kỷ 19 . Trở lại quê hương sau nhiều năm xa cách , với tấm bằng Tráng Sỹ hạng 1 do Liên Đoàn Type Thuật cấp , anh đã được Đức Vua cử làm đại tướng thống lãnh 3 quân chống lại giặc Ô Qua xâm lăng . Đoàn quân của anh sẽ gồm N đại đội , đại đội i có A[i] ( > 0 ) người . Quân sỹ trong 1 đại đội sẽ đứng thành 1 cột từ người 1 -> người A[i] , như vậy binh sỹ sẽ đứng thành N cột . Vì Vân Tiên quyết 1 trận sẽ đánh bại quân Ô Qua nên đã cử ra 1 quân đoàn hùng mạnh nhất . Trong sử cũ chép rằng , quân đoàn của Vân Tiên cử ra lúc đó là một nhóm các đại đội có chỉ số liên tiếp nhau ( tức là đại đội i , i + 1 , … j ) . Vì sử sách thì mối mọt hết cả nên chỉ biết được mỗi thế . Ngoài ra theo giang hồ đồn đại thì sức mạnh của 1 quân đoàn = số người của đại đội ít người nhất * số đại đội được chọn . Nhiệm vụ của bạn là dựa trên các thông số của các nhà khảo cổ có được , hãy cho biết quân đoàn mà Vân Tiên đã chọn ra là từ đại đội nào đến đại đội nào . Chú ý nếu có nhiều phương án thì ghi ra phương án mà chỉ số của đại đội đầu tiên được chọn là nhỏ nhất .

Bài này O(N) mới thực sự coi là accept . Còn lại O(NlogN) , O(N^2) thì đó là do bạn may mắn accept thôi.

Input

Dòng 1 : Số T là số bộ test .
T nhóm dòng tiếp theo , mỗi nhóm dòng mô tả 1 bộ test . Nhóm dòng thứ i :
Dòng 1: N ( <= 30000 )
Dòng 2: N số nguyên mô tả N số A[1] , A[2] , … A[N] ( các số nguyên dương <= 30000 ).
.

Output

Kết quả mỗi test ghi ra trên 1 dòng , gồm 3 số : sức mạnh quân đoàn mạnh nhất , chỉ số của đại đội đầu tiên và chỉ số của đại đội cuối cùng được chọn .

Example 

Input:
2
4
3 4 3 1
4
1 2 1 3

Output:
9 1 3
4 1 4

  • Người up: hard7771988