Để 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.

Cho đến nay, thuật toán yêu thích của cô là “sắp xếp nổi bọt”. Dưới đây là cách cài đặt ban đầu của Bessie bằng mã dành cho bò để sắp xếp một mảng \(A\) có độ dài \(N\).

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Hóa ra lệnh moo trong mã dành cho bò không làm gì ngoài việc in ra moo. Thật kỳ lạ, Bessie dường như nhất quyết chèn lệnh này vào nhiều vị trí trong mã của mình.

Sau khi thử mã trên một số mảng, Bessie nhận ra một điều thú vị: trong khi các phần tử lớn có thể được đẩy về cuối mảng rất nhanh, các phần tử nhỏ có thể mất rất nhiều thời gian để “nổi” lên đầu mảng (cô nghi rằng thuật toán có tên như vậy chính vì lý do này). Để cố gắng giảm bớt vấn đề, Bessie sửa mã để trong mỗi vòng lặp chính, mảng được quét xuôi rồi quét ngược, nhờ đó cả phần tử lớn lẫn phần tử nhỏ đều có cơ hội được đẩy đi một quãng xa trong mỗi vòng lặp chính. Mã của cô giờ đây như sau:

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

Với một mảng đầu vào, hãy dự đoán mã đã sửa đổi của Bessie sẽ in moo bao nhiêu lần.

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 số lần moo được in.

Ví dụ

5
1
8
5
3
2

2

Nguồn

USACO 2018 US Open Contest, Gold — Out of Sorts

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