Tại một trung tâm thương mại, người ta lắp một băng nhạc vào máy phát. Khách chỉ cần nhấn phím ứng với bài muốn nghe; máy sẽ tìm từ đầu băng, quay băng bỏ qua các bài trước đó rồi phát bài được chọn. Tốc độ băng không đổi nên thời gian quay bỏ qua một bài bằng thời gian phát bài đó. Băng ghi được N bài, mỗi bài có thời lượng (phút) đã biết. Trung bình trong ngày, các bài được chọn với tần suất như nhau. Hãy sắp xếp thứ tự ghi các bài trên băng để tổng thời gian quay băng trung bình mỗi ngày là nhỏ nhất (tương đương tổng các thời gian tích lũy khi truy cập từ đầu là nhỏ nhất).

Dữ liệu vào (NHAC.INP): gồm 2 dòng.
Dòng 1: số tự nhiên N (số lượng bài hát).
Dòng 2: N số nguyên dương là thời lượng (phút) của từng bài, cách nhau một dấu cách (bài i có thời lượng a_i).

Dữ liệu ra (NHAC.OUT):
In N dòng mô tả thứ tự ghi trên băng. Mỗi dòng gồm hai số nguyên j d cách nhau một dấu cách, trong đó j là chỉ số bài hát được ghi ở vị trí này, d là thời gian tích lũy tính từ đầu băng đến hết bài này (tổng thời lượng các bài đứng trước cộng thời lượng bài này).
Dòng thứ N+1 ghi tổng của tất cả các thời gian tích lũy ở trên.

Ví dụ

NHAC.INP
3
8 3 4
  

NHAC.OUT
2 3
3 7
1 15
25