Để 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 Bessie cài đặt thuật toán này 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.

Với một mảng đầu vào, hãy dự đoán mã 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
5
3
8
2

4

Nguồn

USACO 2018 US Open Contest, Silver — Out of Sorts

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