시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 957 189 124 20.667%

문제

에린은 엔지니어이자, 기차를 운전하는 기관사입니다. 또한 그녀는 각 열차를 구성하는 차량을 배열하는 일도 합니다. 그녀는 차량들을 정렬할 때, 열차의 전면에 가장 무거운 차량을 놓고, 후미로 갈수록 중량이 감소하는 순서로 차량을 넣는 것을 좋아합니다.

불행하게도, 차량을 배열하는 일은 쉽지 않습니다. 기존에 구성된 열차에 다른 차량을 끼워넣는 일은 비실용적이어서 하지 않기에, 한 차량은 오로지 열차의 전면 혹은 후미에만 추가하는 것이 가능합니다.

차량들은 미리 준비된 순서에 따라 역에 도착합니다. 에린은 각 차량이 기차역에 도착할 때, 전면 혹은 후미에 차량을 추가하거나, 차량을 열차에 추가하는 것을 거부할 수 있습니다. 에린이 최종적으로 만든 열차는 가능한 길어야(많은 차량으로 구성되어야)하지만, 그 과정에서 열차는 에린이 배열하고자하는 정렬 순서에 맞아야 합니다.

각 차량이 역에 도착하는 순서대로 차량들의 중량이 주어질 때, 에린이 만들 수 있는 가장 긴 열차배열의 길이(=차량의 수)는 얼마입니까?

입력

첫째 줄에 차량의 수를 나타내는 N (0 <= N <= 2000)이 주어집니다. 이후 N개의 각 줄에는 음이 아닌 차량의 무게가 주어집니다. (단, 서로 다른 두 차량의 무게가 같은 일은 발생하지 않습니다.)

출력

에린이 만들 수 있는 가장 긴 열차의 길이를 출력하세요.

예제 입력 1

3
1
2
3

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6IjQxOTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZjRcdWNjMjhcdWM4MTVcdWI4MmMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzVkMFx1YjliMFx1Yzc0MCBcdWM1ZDRcdWM5YzBcdWIyYzhcdWM1YjRcdWM3NzRcdWM3OTAsIFx1YWUzMFx1Y2MyOFx1Yjk3YyBcdWM2YjRcdWM4MDRcdWQ1NThcdWIyOTQgXHVhZTMwXHVhZDAwXHVjMGFjXHVjNzg1XHViMmM4XHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVhZGY4XHViMTQwXHViMjk0IFx1YWMwMSBcdWM1ZjRcdWNjMjhcdWI5N2MgXHVhZDZjXHVjMTMxXHVkNTU4XHViMjk0IFx1Y2MyOFx1YjdjOVx1Yzc0NCBcdWJjMzBcdWM1ZjRcdWQ1NThcdWIyOTQgXHVjNzdjXHViM2M0IFx1ZDU2OVx1YjJjOFx1YjJlNC4gXHVhZGY4XHViMTQwXHViMjk0IFx1Y2MyOFx1YjdjOVx1YjRlNFx1Yzc0NCBcdWM4MTVcdWI4MmNcdWQ1NjAgXHViNTRjLCBcdWM1ZjRcdWNjMjhcdWM3NTggXHVjODA0XHViYTc0XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWJiMzRcdWFjNzBcdWM2YjQgXHVjYzI4XHViN2M5XHVjNzQ0IFx1YjE5M1x1YWNlMCwgXHVkNmM0XHViYmY4XHViODVjIFx1YWMwOFx1YzIxOFx1Yjg1ZCBcdWM5MTFcdWI3YzlcdWM3NzQgXHVhYzEwXHVjMThjXHVkNTU4XHViMjk0IFx1YzIxY1x1YzExY1x1Yjg1YyBcdWNjMjhcdWI3YzlcdWM3NDQmbmJzcDtcdWIxMjNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzg4Ylx1YzU0NFx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViZDg4XHVkNTg5XHVkNTU4XHVhYzhjXHViM2M0LCBcdWNjMjhcdWI3YzlcdWM3NDQgXHViYzMwXHVjNWY0XHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWMyN2RcdWM5YzAgXHVjNTRhXHVjMmI1XHViMmM4XHViMmU0LiBcdWFlMzBcdWM4NzRcdWM1ZDAgXHVhZDZjXHVjMTMxXHViNDFjIFx1YzVmNFx1Y2MyOFx1YzVkMCBcdWIyZTRcdWI5NzggXHVjYzI4XHViN2M5XHVjNzQ0IFx1YjA3Y1x1YzZjY1x1YjEyM1x1YjI5NCBcdWM3N2NcdWM3NDAgXHViZTQ0XHVjMmU0XHVjNmE5XHVjODAxXHVjNzc0XHVjNWI0XHVjMTFjIFx1ZDU1OFx1YzljMCBcdWM1NGFcdWFlMzBcdWM1ZDAsIFx1ZDU1YyBcdWNjMjhcdWI3YzlcdWM3NDAgXHVjNjI0XHViODVjXHVjOWMwIFx1YzVmNFx1Y2MyOFx1Yzc1OCBcdWM4MDRcdWJhNzQgXHVkNjM5XHVjNzQwIFx1ZDZjNFx1YmJmOFx1YzVkMFx1YjljYyBcdWNkOTRcdWFjMDBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YWMwMFx1YjJhNVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzI4XHViN2M5XHViNGU0XHVjNzQwIFx1YmJmOFx1YjlhYyBcdWM5MDBcdWJlNDRcdWI0MWMgXHVjMjFjXHVjMTFjXHVjNWQwIFx1YjUzMFx1Yjc3YyBcdWM1ZWRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTY5XHViMmM4XHViMmU0LiBcdWM1ZDBcdWI5YjBcdWM3NDAgXHVhYzAxIFx1Y2MyOFx1YjdjOVx1Yzc3NCBcdWFlMzBcdWNjMjhcdWM1ZWRcdWM1ZDAgXHViM2M0XHVjYzI5XHVkNTYwIFx1YjU0YywgXHVjODA0XHViYTc0IFx1ZDYzOVx1Yzc0MCBcdWQ2YzRcdWJiZjhcdWM1ZDAgXHVjYzI4XHViN2M5XHVjNzQ0IFx1Y2Q5NFx1YWMwMFx1ZDU1OFx1YWM3MFx1YjA5OCwgXHVjYzI4XHViN2M5XHVjNzQ0IFx1YzVmNFx1Y2MyOFx1YzVkMCBcdWNkOTRcdWFjMDBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YWM3MFx1YmQ4MFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWM1ZDBcdWI5YjBcdWM3NzQgXHVjZDVjXHVjODg1XHVjODAxXHVjNzNjXHViODVjIFx1YjljY1x1YjRlMCBcdWM1ZjRcdWNjMjhcdWIyOTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWUzOFx1YzViNFx1YzU3YyhcdWI5Y2VcdWM3NDAgXHVjYzI4XHViN2M5XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YzViNFx1YzU3YylcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YWRmOCBcdWFjZmNcdWM4MTVcdWM1ZDBcdWMxMWMgXHVjNWY0XHVjYzI4XHViMjk0IFx1YzVkMFx1YjliMFx1Yzc3NCBcdWJjMzBcdWM1ZjRcdWQ1NThcdWFjZTBcdWM3OTBcdWQ1NThcdWIyOTQgXHVjODE1XHViODJjIFx1YzIxY1x1YzExY1x1YzVkMCBcdWI5ZGVcdWM1NDRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjYzI4XHViN2M5XHVjNzc0IFx1YzVlZFx1YzVkMCZuYnNwO1x1YjNjNFx1Y2MyOVx1ZDU1OFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjYzI4XHViN2M5XHViNGU0XHVjNzU4IFx1YzkxMVx1YjdjOVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWM1ZDBcdWI5YjBcdWM3NzQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YWUzNCBcdWM1ZjRcdWNjMjhcdWJjMzBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0KD1cdWNjMjhcdWI3YzlcdWM3NTggXHVjMjE4KVx1YjI5NCBcdWM1YmNcdWI5YzhcdWM3ODVcdWIyYzhcdWFlNGM/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2MyOFx1YjdjOVx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE4gKDAgJmx0Oz0gTiAmbHQ7PSAyMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1Yzc3NFx1ZDZjNCBOXHVhYzFjXHVjNzU4IFx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzRjXHVjNzc0IFx1YzU0NFx1YjJjYyBcdWNjMjhcdWI3YzlcdWM3NTggXHViYjM0XHVhYzhjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC4gKFx1YjJlOCwmbmJzcDtcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWNjMjhcdWI3YzlcdWM3NTggXHViYjM0XHVhYzhjXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWM3N2NcdWM3NDAgXHViYzFjXHVjMGRkXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzJiNVx1YjJjOFx1YjJlNC4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNWQwXHViOWIwXHVjNzc0IFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWFlMzQgXHVjNWY0XHVjYzI4XHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMxMzhcdWM2OTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDE5OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRyYWluc29ydGluZyIsImRlc2NyaXB0aW9uIjoiPHA+RXJpbiBpcyBhbiBlbmdpbmVlci4gU2hlIGRyaXZlcyB0cmFpbnMuIFNoZSBhbHNvIGFycmFuZ2VzIHRoZSBjYXJzIHdpdGhpbiBlYWNoIHRyYWluLiBTaGUgcHJlZmVycyB0byBwdXQgdGhlIGNhcnMgaW4gZGVjcmVhc2luZyBvcmRlciBvZiB3ZWlnaHQsIHdpdGggdGhlIGhlYXZpZXN0IGNhciBhdCB0aGUgZnJvbnQgb2YgdGhlIHRyYWluLjxcL3A+XHJcblxyXG48cD5VbmZvcnR1bmF0ZWx5LCBzb3J0aW5nIHRyYWluIGNhcnMgaXMgbm90IGVhc3kuIE9uZSBjYW5ub3Qgc2ltcGx5IHBpY2sgdXAgYSBjYXIgYW5kIHBsYWNlIGl0IHNvbWV3aGVyZSBlbHNlLiBJdCBpcyBpbXByYWN0aWNhbCB0byBpbnNlcnQgYSBjYXIgd2l0aGluIGFuIGV4aXN0aW5nIHRyYWluLiBBIGNhciBtYXkgb25seSBiZSBhZGRlZCB0byB0aGUgYmVnaW5uaW5nIGFuZCBlbmQgb2YgdGhlIHRyYWluLjxcL3A+XHJcblxyXG48cD5DYXJzIGFycml2ZSBhdCB0aGUgdHJhaW4gc3RhdGlvbiBpbiBhIHByZWRldGVybWluZWQgb3JkZXIuIFdoZW4gZWFjaCBjYXIgYXJyaXZlcywgRXJpbiBjYW4gYWRkIGl0IHRvIHRoZSBiZWdpbm5pbmcgb3IgZW5kIG9mIGhlciB0cmFpbiwgb3IgcmVmdXNlIHRvIGFkZCBpdCBhdCBhbGwuIFRoZSByZXN1bHRpbmcgdHJhaW4gc2hvdWxkIGJlIGFzIGxvbmcgYXMgcG9zc2libGUsIGJ1dCB0aGUgY2FycyB3aXRoaW4gaXQgbXVzdCBiZSBvcmRlcmVkIGJ5IHdlaWdodC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gdGhlIHdlaWdodHMgb2YgdGhlIGNhcnMgaW4gdGhlIG9yZGVyIGluIHdoaWNoIHRoZXkgYXJyaXZlLCB3aGF0IGlzIHRoZSBsb25nZXN0IHRyYWluIHRoYXQgRXJpbiBjYW4gbWFrZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgMCAmbHQ7PSBuICZsdDs9IDIwMDAsIHRoZSBudW1iZXIgb2YgY2Fycy4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIG4gbGluZXMgY29udGFpbnMgYSBub24tbmVnYXRpdmUgaW50ZWdlciBnaXZpbmcgdGhlIHdlaWdodCBvZiBhIGNhci4gTm8gdHdvIGNhcnMgaGF2ZSB0aGUgc2FtZSB3ZWlnaHQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGEgc2luZ2xlIGludGVnZXIgZ2l2aW5nIHRoZSBudW1iZXIgb2YgY2FycyBpbiB0aGUgbG9uZ2VzdCB0cmFpbiB0aGF0IGNhbiBiZSBtYWRlIHdpdGggdGhlIGdpdmVuIHJlc3RyaWN0aW9ucy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=