最近越來越多的人都投身股市，阿福也有點(diǎn)心動(dòng)了。謹(jǐn)記著“股市有風(fēng)險(xiǎn)，入市需謹(jǐn)慎”，阿福決定先來研究一下簡(jiǎn)化版的股票買賣問題。
假設(shè)阿福已經(jīng)準(zhǔn)確預(yù)測(cè)出了某只股票在未來N天的價(jià)格，他希望買賣兩次，使得獲得的利潤(rùn)最高。為了計(jì)算簡(jiǎn)單起見，利潤(rùn)的計(jì)算方式為賣出的價(jià)格減去買入的價(jià)格。
同一天可以進(jìn)行多次買賣。但是在第一次買入之后，必須要先賣出，然后才可以第二次買入。
現(xiàn)在，阿福想知道他最多可以獲得多少利潤(rùn)。

輸入的第一行是一個(gè)整數(shù)T(T≤50)，表示一共有T組數(shù)據(jù)。
接下來的每組數(shù)據(jù)，第一行是一個(gè)整數(shù)N(1≤N≤100,000)，表示一共有N天。第二行是 N 個(gè)被空格分開的整數(shù)，表示每天該股票的價(jià)格。該股票每天的價(jià)格的絕對(duì)值均不會(huì)超過1,000,000。

對(duì)于第一組樣例，阿?？梢缘?次在第1天買入（價(jià)格為5），然后在第2天賣出（價(jià)格為14）。第2次在第3天買入（價(jià)格為-2），然后在第7天賣出（價(jià)格為17）。一共獲得的利潤(rùn)是(14-5)+(17-(-2))=28。
對(duì)于第二組樣例，阿?？梢缘?次在第1天買入（價(jià)格為6），然后在第2天賣出（價(jià)格為8）。第2次仍然在第2天買入，然后在第2天賣出。一共獲得的利潤(rùn)是8-6=2。
對(duì)于第三組樣例，由于價(jià)格一直在下跌，阿?？梢噪S便選擇一天買入之后迅速賣出。獲得的最大利潤(rùn)為0。

編程練習(xí) 動(dòng)態(tài)規(guī)劃 基礎(chǔ)