Trong các hoán vị, hai hoán vị được coi là có quan hệ nếu hoán vị này có thể nhận được từ hoán vị kia sau một số thao tác thuộc một trong ba loại sau:

• Dịch phải: (~x_1~,~x_2~,~x_3~,...,~x_n~) -> (~x_{n}~,~x_1~,~x_2~,...,~x_{n-1}~)

• Dịch trái: (~x_1~,~x_2~,~x_3~,...,~x_n~) -> (~x_2~,~x_3~,...,~x_n~, ~x_1~)

• Đảo ngược: (~x_1~,~x_2~,~x_3~,...,~x_n~) -> (~x_{n}~, ~x_{n-1}~,...., ~x_2~, ~x_1~)

Ví dụ, (1,2,3) và (2,1,3) là hai hoán vị có quan hệ do (2,1,3) có thể nhận được từ (1,2,3) bằng cách:

• Dịch phải: (1,2,3) -> (3,1,2)
• Đảo ngược: (3,1,2) -> (2,1,3)
• Các hoán vi của tập {1,2,...,n} được liệt kê theo thứ tự từ điển, một hoán vị sẽ không được liệt kê nếu trước nó có một hoán vị có quan hệ với nó đã được liệt kê. Số hiệu của hoán vị là số thứ tự của hoán vị. Hãy đếm số lượng hoán vị trong từ điển và cho trước một hoán vị, tìm số thứ tự của hoán vị có quan hệ với nó trong từ điển trên

Dữ liệu vào:

• Dòng đầu tiên ghi sốnguyên dương N (N≤50) • Dòng tiếp theo ghi một hoán vị của {1,...,n}

Kết quả ghi ra:

• Dòng đầu tiên ghi tổng số hoán vị trong từ điển • Dòng thứ hai ghi số thứ tự của hoán vị có quan hệ với hoán vị đã cho ở trong từ điển • Dòng thứ ba ghi hoán vị có quan hệ với hoán vị đã cho trong từ điển

Ví dụ:

INPUT

5
1 5 3 2 4

OUTPUT

12
11
1 4 2 3 5