Trò chơi vô tri :>

Points: 2.3 (partial)

Time limit: 1.0s

JAVA11 2.0s

Memory limit: 256M

Author:

Problem type

Hai bạn Chẵn và Lẻ quen nhau trong một cuộc thi lập trình. Chẵn thích số chẵn, và Lẻ thích số lẻ, cả hai bạn đều có giải cao. Trong buổi lễ trao giải, Ban tổ chức đã có một trò chơi trí tuệ dành cho hai bạn. Chẵn và Lẻ cùng chơi một lượt. Nội dung trò chơi như sau:

Cho một vòng tròn được chia thành \(n\) vạch cách đều (\(n\) là một số chẵn). Các vạch được đánh chỉ số từ 1 đến \(n\) theo chều kim đồng hồ. Tại vạch \(i\) có một số nguyên dương \(a_{i}\) \((1 \le a_i \le n)\). Dãy gồm \(n\) số \(a_1, a_2, a_3, ..., a_n\) tạo thành một hoán vị của \(n\) số nguyên \(1, 2, 3, ..., n\). Hai bạn Chẵn và Lẻ phải lập trình điều khiển robot di chuyển quanh vòng tròn để xóa số.

Robot của Lẻ xuất phát từ vạch \(1\), di chuyển theo chiều kim đồng hồ. Robot có thể xóa số ở vạch, tuy nhiên các số phải xóa lần lượt là \(1, 3, 5, ..., n - 1\). Tức là số \(1\) được xóa đầu tiên, rồi đến số \(3, ...,\) số \(n - 1\) được xóa cuối cùng. Khi xóa xong và di chuyển đến vạch \(1\) và dừng lại, được tính là \(1\) vòng.

Robot của Chẵn di chuyển tương tự, tuy nhiên chỉ được xóa lần lượt các số chẵn.

Hai bạn cần đưa ra số vòng mà robot của mình cần di chuyển để xóa hết các số cần xóa. Bạn nào có thể đưa ra kết quả đúng và nhanh sẽ được nhận thêm phần thưởng của Ban tổ chức.

Tất nhiên là chẳng có bạn Chẵn và Lẻ nào ở đây cả :))) Nhiệm vụ của bạn đang đọc cái đề dài dòng này là tính số vòng mà hai robot cần di chuyển để xóa hết các số cần xóa.

Chúc các bạn full AC để được nhận lì xì từ Tú Anh :>

Input

Dòng \(1\) ghi số nguyên dương chẵn \(n (2 \le n \le 2000000)\).
Dòng \(2\) ghi \(n\) số nguyên dương \(a_1, a_2, a_3, ..., a_n\) là hoán vị của \(n\) số \(1, 2, 3, ..., n\). Các số được ghi cách nhau bởi dấu cách.