Ирена е присутна во публика за време на свечената церемонија за доделување награди на Државниот натпревар по информатика, и на подиумот таа гледа N ученици наредени еден до друг во една линија. За секој од овие ученици, Ирена знае колку поени тие освоиле на натпреварот. Па така, на пример, според освоените поени, учениците може да се наредени во следниот редослед:

    50 150 200 50 300 250 250 260 100

На Ирена и е многу интересен проблемот на пронаоѓање на најдолга растечка подниза од броеви – односно, во нашиот случај, наоѓање на листа од ученици кои, гледано од лево на десно, имаат растечки број на поени. За примерот даден погоре, тоа се 5 ученици, т.е. {50, 150, 200, 250, 260}. Забележете како секој следен број е поголем од претходниот, и дека учениците не мора да се соседни (да се наоѓаат еден до друг).

Бидејќи Ирена брзо ја пресметала должината на најдолгата растечка подниза од поени на учениците, таа сега сака да реши P прашања од следниот тип: “Колку ќе изнесуваше најдолгата растечка подниза, ако Xi-тиот ученик всушност имаше освоено Yi поени?”

На пример, доколку во низата дадена погоре, последниот ученик имаше освоено 300 поени, тогаш ќе постоеше растечка подниза од поени на 6 ученици {50, 150, 200, 250, 260, 300}.

Напишете програма која ќе одговори точно на овие P прашања. Сите прашања се одговараат индивидуално и се независни едни од други, т.е. не влијаат на наредните прашања.

Влез

Во првиот ред се запишани два цели броја N и P (1 <= N, P <= 300000), кои го означуваат бројот на ученици и прашања. Во вториот ред се запишани N позитивни цели броеви (помали или еднакви на 1000000000), кои ги означуваат поените кои ги освоиле учениците, гледано од лево на десно на подиумот.

Во секој од наредните P редови се запишани по два цели броја Xi (1 <= Xi <= N) и Yi (1 <= Yi <= 1000000000).

Забелешка: Во тест случаи кои носат најмалку 15% од поените, броевите N и P ќе бидат помали или еднакви на 20.
Во други тест случаи кои носат најмалку 20% од поените, броевите N и P ќе бидат помали или еднакви на 100.
За дополнителни 15% од поените, за сите прашања ќе важи Yi=1.

Излез

За секое од P-те прашања, во посебен ред, отпечатете ја должината на најдолгата растечка подниза.

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

Временско ограничување: 2 seconds
Мемориско ограничување: 256 megabytes

Примери

влез
9 3
50 150 200 50 300 250 250 260 100
9 300
1 500
2 150

излез
6
4
5