Problem4416--电路规划

4416: 电路规划

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 1
[Status] [Submit] [Creator:]

Description


电路板上，左右各有N个接触点，左边的每个触点都有一条线路连接到右边的触点，但是有些线路相交。现在要去除部分线路，使得任何线路都不相交，在触点相交是允许的。求最多可以保留下来多少条线路。



Input


第1行，一个数N。

第2行N个数，依次表示电路板左边触点通过线路连接到右边触点的编号。

Output


一个数，表示最多可以保留下来的线路数。

Sample Input Copy 

6
4 2 6 3 1 5

Sample Output Copy 

3

HINT

数据范围
N<=2000

Source/Category

 140_T05' 
[Submit] [Status]