Để chuẩn bị cho những cơ hội nghề nghiệp lâu dài bên ngoài trang trại, cô bò Bessie đã bắt đầu học các thuật toán từ nhiều trang web lập trình trực tuyến. Hai thuật toán yêu thích của cô là “sắp xếp nổi bọt” và “sắp xếp nhanh”, nhưng thật không may, Bessie rất dễ nhầm lẫn hai thuật toán này và cuối cùng lại cài đặt một thuật toán lai khá kỳ lạ!

Ta gọi vị trí nằm giữa hai phần tử \(i\) và \(i+1\) trong một mảng \(A\) là một “điểm phân hoạch” nếu giá trị lớn nhất trong \(A[...i]\) không lớn hơn giá trị nhỏ nhất trong \(A[i+1 \ldots]\). Bessie nhớ rằng sắp xếp nhanh sắp xếp lại một mảng sao cho mảng có một điểm phân hoạch, rồi đệ quy sắp xếp hai phía \(A[...i]\) và \(A[i+1 \ldots]\). Tuy nhiên, dù đã nhận ra chính xác rằng tất cả các điểm phân hoạch trong một mảng có thể được xác định trong thời gian tuyến tính, cô lại quên mất sắp xếp nhanh phải sắp xếp lại mảng như thế nào để nhanh chóng tạo ra một điểm phân hoạch! Trong một quyết định có thể là sai lầm thuật toán tồi tệ nhất lịch sử các thuật toán sắp xếp, cô không may quyết định dùng sắp xếp nổi bọt cho nhiệm vụ này.

Dưới đây là phác thảo cách cài đặt ban đầu của Bessie để sắp xếp một mảng \(A\). Trước tiên, cô viết một hàm đơn giản thực hiện một lượt sắp xếp nổi bọt:

bubble_sort_pass (A) {
   for i = 0 to length(A)-2
      if A[i] > A[i+1], swap A[i] and A[i+1]
}

Sau đó, mã đệ quy cho hàm sắp xếp nhanh (kiểu gần giống) của cô có cấu trúc như sau:

quickish_sort (A) {
   if length(A) = 1, return
   do { // Main loop
      work_counter = work_counter + length(A)
      bubble_sort_pass(A)
   } while (no partition points exist in A)
   divide A at all partition points; recursively quickish_sort each piece
}

Bessie tò mò không biết mã của mình sẽ chạy nhanh đến đâu. Để đơn giản, cô cho rằng mỗi vòng lặp chính cần thời gian tuyến tính, nên trong vòng lặp, cô tăng một biến toàn cục có tên work_counter thêm một lượng tương ứng để theo dõi tổng khối lượng công việc mà thuật toán thực hiện.

Với một mảng đầu vào, hãy dự đoán giá trị cuối cùng của work_counter sau khi mảng được xử lý bởi quickish_sort.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 100\,000\)). \(N\) dòng tiếp theo mô tả lần lượt \(A[0] \ldots A[N-1]\); mỗi phần tử là một số nguyên thuộc khoảng \(0 \ldots 10^9\). Các phần tử đầu vào không nhất thiết đôi một khác nhau.

Dữ liệu ra

In ra giá trị cuối cùng của work_counter.

Ví dụ

7
20
2
3
4
9
8
7

12

Nguồn

USACO 2018 US Open Contest, Platinum — Out of Sorts

Tác giả bài toán: Brian Dean.