시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 256 MB 1871 596 450 33.657%

문제

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

  1. 주식 하나를 산다.
  2. 원하는 만큼 가지고 있는 주식을 판다.
  3. 아무것도 안한다.

홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

입력

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.

출력

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

예제 입력 1

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

예제 출력 1

0
10
5
W3sicHJvYmxlbV9pZCI6IjExNTAxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjOGZjXHVjMmRkIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ2NGRcdWM5MDBcdWM3NzRcdWIyOTQgXHVjNjk0XHVjOTk4IFx1YzhmY1x1YzJkZFx1YzVkMCBcdWJlNjBcdWM4MzhcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjI5NCBcdWJiZjhcdWI3OThcdWI5N2MgXHViMGI0XHViMmU0XHViY2Y0XHViMjk0IFx1YjIwOFx1Yzc3NCBcdWI2ZjBcdWM1YjRcdWIwOTgsIFx1YjBhMCBcdWJjYzRcdWI4NWMgXHVjOGZjXHVhYzAwXHViOTdjIFx1YzYwOFx1YzBjMVx1ZDU1OFx1YWNlMCBcdWM1YjhcdWM4MWNcdWIwOTggXHVhZGY4XHVhYzhjIFx1YjlkZVx1YzU0NFx1YjVhOFx1YzViNFx1YzljNFx1YjJlNC4gXHViOWU0XHVjNzdjIFx1YWRmOFx1YjI5NCBcdWM1NDRcdWI3OTggXHVjMTM4IFx1YWMwMFx1YzljMCBcdWM5MTEgXHVkNTVjIFx1ZDU4OVx1YjNkOVx1Yzc0NCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHVjOGZjXHVjMmRkIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMwYjBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzZkMFx1ZDU1OFx1YjI5NCBcdWI5Y2NcdWQwN2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWM4ZmNcdWMyZGRcdWM3NDQgXHVkMzEwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM1NDRcdWJiMzRcdWFjODNcdWIzYzQgXHVjNTQ4XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1ZDY0ZFx1YzkwMFx1Yzc3NFx1YjI5NCBcdWJiZjhcdWI3OThcdWI5N2MgXHVjNjA4XHVjMGMxXHVkNTU4XHViMjk0IFx1YjZmMFx1YzViNFx1YjA5YyBcdWM1NDhcdWJhYTlcdWM3NDQgXHVhYzAwXHVjODRjXHVjOWMwXHViOWNjLCBcdWM1YjRcdWI1YmJcdWFjOGMgXHVkNTc0XHVjNTdjIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWNkNWNcdWIzMDAgXHVjNzc0XHVjNzc1XHVjNzQ0IFx1YzViYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YmFhOFx1Yjk3OFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjIFx1YjJmOVx1YzJlMFx1YzVkMFx1YWM4YyBcdWIwYTAgXHViY2M0XHViODVjIFx1YzhmY1x1YzJkZFx1Yzc1OCBcdWFjMDBcdWFjYTlcdWM3NDQgXHVjNTRjXHViODI0XHVjOGZjXHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwIFx1Yzc3NFx1Yzc3NVx1Yzc3NCBcdWM1YmNcdWI5YzhcdWIwOTggXHViNDE4XHViMjk0XHVjOWMwIFx1YWNjNFx1YzBiMFx1Yzc0NCBcdWQ1NzRcdWIyZWNcdWI3N2NcdWFjZTAgXHViZDgwXHVkMGMxXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YjBhMCBcdWMyMThcdWFjMDAgM1x1Yzc3Y1x1Yzc3NFx1YWNlMCBcdWIwYTAgXHViY2M0XHViODVjIFx1YzhmY1x1YWMwMFx1YWMwMCAxMCwgNywgNlx1Yzc3YyBcdWI1NGMsIFx1YzhmY1x1YWMwMFx1YWMwMCBcdWFjYzRcdWMxOGQgXHVhYzEwXHVjMThjXHVkNTU4XHViYmMwXHViODVjIFx1Y2Q1Y1x1YjMwMCBcdWM3NzRcdWM3NzVcdWM3NDAgMFx1Yzc3NCBcdWI0MWNcdWIyZTQuIFx1YWRmOFx1YjdlY1x1YjA5OCBcdWI5Y2NcdWM1N2QgXHViMGEwIFx1YmNjNFx1Yjg1YyBcdWM4ZmNcdWFjMDBcdWFjMDAgMywgNSwgOVx1Yzc3YyBcdWI1NGNcdWIyOTQgXHVjYzk4XHVjNzRjIFx1YjQ1MCBcdWIwYTBcdWM1ZDAgXHVjOGZjXHVjMmRkXHVjNzQ0IFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWMwYWNcdWFjZTAsIFx1YjljOFx1YzljMFx1YjljOVx1YjBhMCBcdWIyZTQgXHVkMzE0XHVjNTQ0IFx1YmM4NFx1YjlhY1x1YmE3NCBcdWM3NzRcdWM3NzVcdWM3NzQgMTBcdWM3NzQgXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4XHVjZjAwXHVjNzc0XHVjMmE0IFx1YmNjNFx1Yjg1YyBcdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjBhMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1Yzc5MFx1YzVmMFx1YzIxOCBOKDIgJmxlOyBOICZsZTsgMSwwMDAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViMGEwIFx1YmNjNCBcdWM4ZmNcdWFjMDBcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHViNGU0XHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMGEwIFx1YmNjNCBcdWM4ZmNcdWFjMDBcdWIyOTQgMTAsMDAwXHVjNzc0XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTQgXHViY2M0XHViODVjIFx1Y2Q1Y1x1YjMwMCBcdWM3NzRcdWM3NzVcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWIyZjVcdWM3NDAgXHViZDgwXHVkNjM4XHVjNzg4XHViMjk0IDY0Yml0IFx1YzgxNVx1YzIxOFx1ZDYxNVx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDQgXHVhYzAwXHViMmE1XHVkNTU4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjExNTAxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU3RvY2siLCJkZXNjcmlwdGlvbiI6IjxwPk1yLiBMaW0gZW5qb3lzIGludmVzdGluZyBpbiBzdG9ja3MuIEhpcyBpbnZlc3RtZW50IHJ1bGVzIGFyZSBhcyBmb2xsb3dzOiBHaXZlbiB0aGUgc3RvY2sgcHJpY2VzIG9mIGEgY29tcGFueSBmb3IgYSBzZXJpZXMgb2YgZGF5cywgZWFjaCBkYXkgaGlzIGFjdGlvbiBpcyBvbmUgb2YgdGhlIGZvbGxvd2luZ3M6PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+QnV5IG9uZSB1bml0IG9mIHN0b2NrLjxcL2xpPlxyXG5cdDxsaT5TZWxsIGFueSBudW1iZXIgb2Ygc3RvY2sgdW5pdHMgeW91IGhhdmUgYWxyZWFkeSBib3VnaHQuPFwvbGk+XHJcblx0PGxpPkRvIG5vdGhpbmcuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+SGUgd2FudHMgdG8ga25vdyB0aGUgZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBwcm9maXQgaGUgb2J0YWluZWQgYW5kIHRoZSBtYXhpbXVtIHBvc3NpYmxlIHByb2ZpdCBieSBwbGFubmluZyB0aGUgYWJvdmUgYWN0aW9ucyBvcHRpbWFsbHkuIFNvLCBoZSBpcyB0cnlpbmcgdG8gY2FsY3VsYXRlIHRoZSBtYXhpbXVtIHByb2ZpdCB0aGF0IGNhbiBiZSBvYnRhaW5lZCBieSBhbiBvcHRpbWFsIHBsYW4gZm9yIGdpdmVuIHRoZSBzdG9jayBwcmljZXMgZm9yIGEgc2VyaWVzIG9mIGRheXMuIEZvciBleGFtcGxlLCBsZXQgdGhlIHN0b2NrIHByaWNlcyBvZiB0aHJlZSBkYXlzIGJlIDEwLCA3LCBhbmQgNi4gVGhlbiB0aGUgbWF4aW11bSBwcm9maXQgaXMgMCBiZWNhdXNlIHRoZSBwcmljZSBkZWNyZWFzZXMgZWFjaCBkYXkuIElmIHRoZSBzdG9jayBwcmljZXMgb2YgdGhyZWUgZGF5cyBhcmUgMywgNSwgYW5kIDksIHRoZSBtYXhpbXVtIHByb2ZpdCBpcyAxMCBvYnRhaW5lZCBieSBidXlpbmcgb25lIHVuaXQgb2Ygc3RvY2sgYXQgZWFjaCBvZiB0aGUgZmlyc3QgdHdvIGRheXMgYW5kIHNlbGxpbmcgdHdvIHN0b2NrIHVuaXRzIGF0IHRoZSB0aGlyZCBkYXkuPFwvcD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIGNhbGN1bGF0aW5nIHRoZSBtYXhpbXVtIHByb2ZpdCB0aGF0IGNhbiBiZSBvYnRhaW5lZCBieSBhbiBvcHRpbWFsIHBsYW4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHN0YXJ0cyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIsIG4gKDIgJmxlOyBuICZsZTsgMSwwMDAsMDAwKSwgd2hlcmUgbiBpcyB0aGUgbnVtYmVyIG9mIGRheXMgaW4gYSBwZXJpb2QuIEluIHRoZSBmb2xsb3dpbmcgbGluZSwgbiBpbnRlZ2VycyByZXByZXNlbnRpbmcgc3RvY2sgcHJpY2VzIG9mIHRoZSBwZXJpb2QgYXJlIGdpdmVuLiBFYWNoIHN0b2NrIHByaWNlIGlzIGdpdmVuIGFzIGFuIGludGVnZXIgYmV0d2VlbiAxIGFuZCAxMCwwMDAsIGluY2x1c2l2ZWx5LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiB0aGUgbWF4aW11bSBwcm9maXQuIFlvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIHJlc3VsdCBmaXRzIGluIGEgc2lnbmVkIDY0LWJpdCBpbnRlZ2VyLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2015 I번