Xây tháp

Tại vương quốc A, có một nàng công chúa xinh đẹp được rất nhiều người yêu mến, nên vào dịp sinh nhật trăng tròn của mình, công chúa được tặng \(n\) món quà hình hộp chữ nhật, các hộp quà được tặng lần lượt theo thứ tự từ \(1\) đến \(n\). Vì quy cách tặng quà nên các hộp quà này có cùng độ dài, độ cao, chỉ khác nhau ở độ rộng (gọi độ rộng là \(r\)), mỗi hộp quà được sơn bởi một trong hai màu xanh hoặc đỏ. Người hầu của công chúa được giao nhiệm vụ nhận quà nên cần phải thực hiện xếp chúng thành tháp quà cao nhất có thể, theo yêu cầu sau:

• Mỗi tầng chỉ xếp \(1\) hộp quà.

• Không xoay chiều các hộp quà.

• Để đặt hộp quà thứ \(i\) lên trên hộp quà thứ \(j\) thì độ rộng của hộp quà \(i\) phải nhỏ hơn độ rộng của hộp quà \(j\).

• Hai hộp quà xếp chồng kề nhau phải có màu sắc khác nhau.

Yêu cầu: Hãy chọn nhiều nhất các hộp quà có thể để xếp chúng thành tháp quà thỏa mãn các yêu cầu trên.

Input

Dữ liệu vào:

• Dòng đầu tiên ghi số \(n\) (\(1 \le n \le 500\,000\)).

• Dòng tiếp theo ghi \(n\) số \(r_1, r_2, \ldots, r_n\) (\(-10^9 \le r_i \le 10^9\), \(r_i \ne 0\)). Trong đó \(r_i > 0\) là khối màu đỏ, \(r_i < 0\) là khối màu xanh, \(|r_i|\) là độ rộng của hộp quà thứ \(i\).

Output

In ra một số nguyên là số lượng hộp quà nhiều nhất có thể xây được.

Example 1

Input:

5
7 -2 6 9 -3

Output:

2

Example 2

Input:

8
11 -9 2 5 18 17 -15 4

Output:

5

Note

Ví dụ 1: các hộp có (độ rộng, màu) là \((7,\text{đỏ})\), \((2,\text{xanh})\), \((6,\text{đỏ})\), \((9,\text{đỏ})\), \((3,\text{xanh})\). Có thể xếp hộp đỏ rộng \(9\) ở dưới và hộp xanh rộng \(3\) ở trên, được \(2\) hộp; không thể xếp được \(3\) hộp vì sau hộp xanh rộng \(3\) chỉ còn hộp xanh rộng \(2\) cùng màu.

Ví dụ 2: chọn các hộp theo độ rộng giảm dần từ dưới lên: đỏ \(18\), xanh \(15\), đỏ \(11\), xanh \(9\), đỏ \(5\) (màu xen kẽ, độ rộng giảm dần), được \(5\) hộp. Không thể được nhiều hơn.