Sau một buổi học Cấu trúc dữ liệu và giải thuật với thầy TICHPX, nqson vừa nghĩ ra một thuật toán Queue Sort có nội dung như sau:

Cho một dãy số gồm n số hạng khác nhau, ta cần tạo ra 2 hảng đợi để sắp xếp n số hạng đó. Hàng đợi đầu tiên (\(qu1\)) chứa tất cả các số trong dãy số từ trái sang phải, hàng đợi thứ hai (\(qu2\)) thì rỗng. Từng bước một, mỗi bước ta thực hiện một trong các trường hợp sau (ưu tiên từ trên xuống dưới):

• Trường hợp 1: Nếu \(qu2\) đang rỗng, ta lấy một tử đầu tiên của \(qu1\) cho vào \(qu2\)
• Trường hợp 2: Nếu phần tử đầu tiên của cả hai hàng đợi đều lớn hơn phần tử cuối cùng của \(qu1\), ta lấy phần tử bé hơn trong hai hàng đợi đó ra khỏi hàng đợi rồi thêm nó vào cuối \(qu1\)
• Trường hợp 3: Nếu phần tử đầu tiên của \(qu1\) lớn hơn phần tử cuối cùng của cả hai hàng đợi, ta lấy phần tử đầu tiên của hàng đợi thứ nhất ra khỏi hàng đợi rồi thêm vào hàng đợi có phần tử cuối cùng lớn hơn
• Trường hợp 4: Nếu một trong hai phần tử đầu tiên của hai hàng đợi lớn hơn phần tử cuối cùng của \(qu1\), ta lấy phần tử lớn hơn trong hai hàng đợi đó ra khỏi hàng đợi rồi thêm nó vào cuối \(qu1\)
• Trường hợp 5: Nếu phần tử đầu tiên của \(qu1\) lớn hơn một trong hai phần tử cuối cùng của hai hàng đợi, ta lấy phần tử đầu tiên của hàng đợi thứ nhất ra khỏi hàng đợi rồi thêm vào hàng đợi có phần tử cuối cùng bé hơn
• Trường hợp 6: Nếu tất cả các trường hợp trên không thỏa mãn, ta lấy phần tử ở đầu hàng đợi có giá trị bé hơn ra khỏi hàng đợi rồi thêm nó vào cuối \(qu1\)

Thực hiện đến khi \(qu1\) không còn phần tử nào, \(qu2\) sẽ chứa dãy số ban đầu được sắp xếp thành công.

In ra tổng số lượng các bước trên.

Giới hạn:

\(n \le 100000\)

Đầu vào

Dòng đầu tiên là một số tự nhiên \(n\)

Dòng tiếp theo chứa \(n\) số trong dãy số đôi một khác nhau

Đầu ra

In ra tổng số lượng các bước để có thể sắp xếp thành công dãy số

Ví dụ 1:

Đầu vào

5
1 2 3 4 5

Đầu ra

5

Ví dụ 2:

Đầu vào

3
2 3 1

Đầu ra

7

Giải thích

Bắt đầu:
    qu1: 2 3 1
    qu2:
B1:
    qu1: 3 1
    qu2: 2
B2:
    qu1: 3 1 2
    qu2:
B3:
    qu1: 1 2
    qu2: 3
B4:
    qu1: 1 2 3
    qu2:
B5:
    qu1: 2 3
    qu2: 1
B6:
    qu1: 3
    qu2: 1 2
B7:
    qu1:
    qu2: 1 2 3