Домино е игра која се игра со домино плочки. Секоја плочка има две страни, и на страните, преку точки, има претставено по еден број: 0, 1, 2,....

На горната слика гледаме 7 домино плочки, складирани во линија. Тоа се плочките (6, 6), (3, 3), (6, 3), (2, 0), (3, 2), (6, 5) и (1, 5).

Нас не интересира само горниот број на секоја плочка. Бидејќи плочките се наредени во линија, можеме да видиме дека броевите ја формираат низата 6, 3, 6, 2, 3, 6, 1.

Во оваа низа, најдолгата растечка подниза е поднизата 2, 3, 6 која што започнува од четвртата плочка и има 3 елементи (растечка подниза овде значи дека секој следен елемент е поголем или еднаков на претходниот, а поднизата се состои од елементи кои се последователни во оригиналната низа).

Да речеме дека смееме некои од плочките да ги свртиме (притоа да си останат на иста позиција во линијата како и претходно). Ако ги свртиме последните 2 плочки, ќе се добие низата 6, 3, 6, 2, 3, 5, 5 . Кај оваа низа, најдолгата растечка подниза е низата 2, 3, 5, 5, со 4 елементи. Со горните плочки ова е најдолгата подниза која може да се постигне, без разлика и ако пробуваме да свртиме други плочки.

Нека ви се дадени по редослед N плочки, и за секоја од нив ги знаете вредностите на парот од броеви (A, B). Ваша задача е да пресметате колку ќе биде долга најдолгата растечка подниза, ако имате право да ги свртите сите плочки кои сакате.

Влез

Во првиот ред е даден позитивен цел број N (N ≤ 100 000).
Во вториот ред се дадени N ненегативни цели броеви кои ги даваат по редослед горните вредности на секоја од плочките (вредноста А од парот (А, В)).
Во третиот ред се дадени N ненегативни цели броеви кои ги даваат по редослед долните вредности на секоја од плочките (вредноста В од парот (А, В)). Притоа, А, В < 1000

Забелешка:
За 9 поени ќе важи: N = 3
За други 15 поени ќе важи: на секоја плочка двата броја се исти (т.е. во (А, В), А=В).
За други 16 поени ќе важи: N < 15
За други 28 поени ќе важи: N < 5000

Излез

Во првиот ред отпечатете од колку елементи ќе се состои најдолгата растечка подниза според барањето во задачата.

Ограничувања

Временско ограничување: 100 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
7
6 3 6 2 3 6 1
6 3 3 0 2 5 5

излез
4

влез
3
2 5 3
2 5 3

излез
2