TL channel của anh Trần Lộc là một kênh Youtube để học thuật toán rất nổi tiếng. Tuy nhiên, anh ấy đang có dự định sẽ chuyển nhượng lại trong mùa hè tới đây. Biết được tin này, đã có ~n~ khách hàng đến muốn mua đấu giá và xếp thành hàng chờ sẵn, mỗi người có một mức tài chính khác nhau (số tiền này là con số nhạy cảm mà họ không muốn cho đối thủ biết, chỉ có anh Lộc là nắm thông tin này). Tuy nhiên vì có sự xô xát xảy ra nên thư ký Trần Nhân của anh muốn sắp xếp các vị khách thành một hàng dọc theo thứ tự tăng dần của mức tài chính. Nhân vừa học được chiêu bubble sort của sếp mình nên đã thực hiện như sau: đi từ đầu dãy, gặp hai khách liên tiếp mà người đứng trước có nhiều tiền hơn người đứng sau thì đổi chỗ. Nhân thực hiện tiếp như vậy cho đến cuối hàng, sau đó lại quay về đầu và làm lại như thế cho đến khi nào không còn ai phải đổi chỗ thì thôi. Tuy nhiên, mỗi lần đổi chỗ hai người thì cũng làm lộ thông tin số tiền của họ cho đối phương biết và đồng thời, bằng cách đó cũng tốn nhiều lần đổi mới xong.

Anh Lộc sau khi biết Nhân sắp xếp như vậy đã rất tức giận và chất vấn Nhân hai vấn đề sau:

• Có bao nhiêu cặp khách đã phải đổi chỗ?
• Số lượng khách lớn nhất đôi một không được đổi chỗ với nhau (tức là chưa lộ thông tin tài chính cho nhau) là bao nhiêu?

Từ thông tin tài chính của những người đứng trong hàng lúc đầu, bạn hãy giúp Nhân trả lời câu hỏi này trước khi anh Lộc đuổi việc bạn ấy nhé.

Input:

Dòng đầu tiên gồm số nguyên dương ~n~ với ~1 \le n \le 10^5.~

Dòng tiếp theo là hoán vị của các số ~1,2,...,n~ ứng với thứ tự tài chính của các vị khách.

Output:

Câu trả lời cho hai câu hỏi của thư ký Nhân khi bị chất vấn.

Sample input 1:

4
2 1 4 3

Sample output 1:

2 2

Sample input 2:

4
1 2 4 3

Sample output 2:

1 3

Giải thích: trong VD1, ta thấy có tất cả 2 lần đổi gồm cặp ~(2,1)~ và ~(4,3)~, ngoài ra ta có thể chọn ra một người trong cặp này, một người trong cặp kia thì hai người đó chưa biết thông tin của nhau; trong VD2, ta thấy chỉ cần 1 lần đổi chỗ, ngoài ra, có thể chọn ba người ~1,2,4~ thì họ đôi một chưa đổi chỗ cho nhau lần nào.