Du lịch bằng cáp treo không chỉ rút ngắn thời gian di chuyển lên đỉnh núi "cưỡi mây" mà còn là dịp ngắm nhìn toàn cảnh thành phố từ trên cao. Các vị trí xuất phát của cáp treo được đặt dọc trên con đường thứ nhất ở ven biển, các vị trí đến sẽ được đặt dọc trên con đường thứ hai đi qua các điểm tham quan đẹp nhất trong thành phố. Hai con đường này không cắt nhau và cùng có hướng từ Đông sang Tây. Ta gọi các số gán cho các điểm là số hiệu của chúng. Cho phép nối hai điểm trên hai đường thẳng có cùng số hiệu.

Trong quá trình khảo sát xây dựng cáp treo, ban quản lý thiết kế phát hiện một số tuyến cắt nhau có nguy cơ xảy ra va chạm do đó cần phải loại bỏ các tuyến này và chỉ xây dựng các tuyến không cắt nhau để đảm bảo an toàn cho khách du lịch.

Yêu cầu: Tìm số tuyến nhiều nhất không cắt nhau.

Dữ liệu vào:

+ Dòng thứ nhất số nguyên dương \(n\ (1 \leq n \leq 10000)\)

+ Dòng thứ hai ghi \(n\) số nguyên \(p_{1},\ p_{2},\ ...,\ p_{n}\), là một hoán vị của số hiệu \(1,\ 2,\ \ldots,\ n\ (1\ \leq \ p_{i} \leq n;\ i = 1..n)\), các số trên cùng một dòng ghi tách nhau một dấu cách.

Kết quả:

+ Ghi một số nguyên là số tuyến nhiều nhất không cắt nhau.

Ví dụ:

Input	Output
9 2 5 3 8 7 4 6 9 1	5

Hình vẽ dưới đây cho 1 ví dụ khi n = 9:

2

5

3

8

7

4

6

9

1

1

2

3

4

5

6

7

8

9

Điểm đến

Xuất phát

Đông

Tây