Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8820

Jo'natishlar soni: 714406

Muhokama yozuvlari: 4541

Yangiliklar soni: 97

Yangiliklar izohlari: 1174


So'ngi izohlar

798. Deque
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

       Deque is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). You have a heap of numbers wich you should to insert them to deque. You should insert numbers in given order. You can insert either to the front or to the back. Any time you can remove an item either from front or from back.  But you can’t insert to deque removed items again. After the end of operations items in deque must be in increasing order and amount of them(size of deque) must be maximal. Your task is to find maximal size of deque.

Input

In the first line given n – the numbers of items(1≤n≤1000). In the second line given values of items in order you should work with them. They are different integer numbers and values may be from -109 to 109.

Output

Output the maximal size of deque wich items in increasing order.

Samples

Input

Output

1

3

1 2 3

3

2

2

2 1

2

 

Avtor: Azat Yusupov
2015 yil Dasturlash bo'yicha Tatu va uning filiallari talabalari o'rtasida jamoaviy olimpiada. Final. Urgench 21-23 aprel.
Mening urinishlarim(0) Muhokama (1) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(18) Barcha urinishlar(81)