Sông Tiền là một trong hai nhánh sông lớn của dòng sông MeKong. Trước đây, việc giao thông qua lại giữa hai bờ sông chủ yếu bằng phà và các tuyến độ ngang. Từ năm 2000, cầu Mỹ Thuận đã được đưa vào sử dụng và sắp tới đây sẽ tiếp tục khánh thành cầu Cao Lãnh nối liền hai bờ sông Tiền. Có thể nói, những công trình này cùng với cầu Cần Thơ và cầu Vàm Cống (cũng sắp hoàn thành) đã góp phần rất lớn trong việc phát triển kinh tế của vùng ĐBSCL, kết nối vùng ĐBSCL gần hơn với TP.HCM và các tỉnh miền Đông Nam bộ. Mặc dù vậy, chúng ta cũng không thể phủ nhận vai trò của những tuyến đò ngang hiện nay vì sự tiện lợi của nó thay vì phải đi vòng những đoạn đường xa để qua sông bằng cầu.

Hiện tại, dọc theo sông Tiền có N tuyến đò ngang đang hoạt động, mỗi tuyến đò đi từ một bến đò ở bờ Bắc sông Tiền sang một bến ở bờ Nam sông Tiền và ngược lại. Các bến đò ở mỗi bờ được đánh số từ 1 đến N theo thứ tự từ thượng nguồn xuống hạ nguồn. Biết rằng, nếu tuyến đò xuất phát từ bền đò i ở bờ Bắc thì sẽ đi sang bền đỏ a, ở bờ Nam (i=1.N, a, = 1..N, ai khác aj với mọi i khác j). Vấn đề phát sinh là giữa một số tuyên đò có hành trình khi sang sông bị giao cắt nhau và như vậy có thế không an toàn cho hành khách vì có thể xảy ra tại nạn va chạm trên sông. Chính vì vậy chính quyền địa phương dự định sẽ cho dừng hoạt động một sô tuyên đò, chỉ giữ lại những tuyển đò mà hành trình của nó không giao cắt với hành trình của những tuyến khác được giữ lại.

Yêu cầu: Hãy tìm một phương án dừng hoạt động một số ít nhất các tuyến đò sao cho những tuyến đò hoạt động còn lại có hành trình không giao cắt nhau.

Dữ liệu vào: Cho từ tệp văn bản TUYENDO.INP có dạng:

• Dòng thứ nhất ghi số nguyên dương N

• Dòng thứ hai ghi N số nguyên dương a1, a2 ..., aN. Giữa các số cách nhau một khoảng cách.

Giới hạn dữ liệu:

Có 20% số điểm ứng với giá trị N ≤ 20

Có 50% số điểm ứng với giá trị N ≤ 10^3

Có 30% số điểm ứng với giá trị N ≤ 10^5

Kết quả: Ghi vào tệp văn bản TUYENDO.OUT gồm một dòng ghi một số nguyên là số tuyến đò ít nhất cần phải dừng hoạt động.

Ví dụ:

Input:

5
3 1 2 5 4

Output:

2

Giải thích: Có ít nhất 2 tuyến đò phải dừng hoạt động là tuyến 1 và 4 hoặc tuyến 1 và 5.