003 - 分割

時間制限 2 秒 / メモリ制限 1024 MB / 得点 100 / x 3 /


TLE
2sec
MLE
1024MB
得点
100

問題文

長さ N の整数列 A = (A1, A2, ..., AN) が与えられる.数列 A の値はすべて異なる.

最大値で数列を分割したとき,最大値より前にある値の和と,最大値より後ろにある値の和を出力せよ.

すなわち,数列 A の最大値を Ax とすると,A1 + A2 + … + Ax-1Ax+1 + Ax+2 + … +AN を出力せよ.

ただし最大値より前に値がない場合,最大値より前にある値の和は 0 になる.

同様に最大値より後ろに値がない場合,最大値より後ろにある値の和は 0 になる.

制約

  • 1 ≦ N ≦ 100
  • 1 ≦ Ai ≦ 2000 (1 ≦ i ≦ N).
  • Ai ≠ Aj (1 ≦ i < j ≦ N).

入力

入力は以下の形式で標準入力から与えられる.
N
A1 A2 AN

出力

出力は 2 行からなる.

1 行目に,整数列 A の,最大値より前にある値の和を出力せよ.

2 行目に,整数列 A の,最大値より後ろにある値の和を出力せよ.

入出力例

入力例 1

5
9 3 16 8 1

出力例 1

12
9

  • この数列の最大値は 16 である.よって 16 より前にある 9,3 の和である 12 と,16 より後ろにある 8,1 の和である 9 を改行区切りで出力する.

入力例 2

6
121 8 5 4 1 3

出力例 2

0
21

  • この数列の最大値は 121 である.121 より前に値はないので最初に 0 を出力する.続けて 121 より後ろにある 8,5,4,1,3 の和である 21 を出力する.

入力例 3

1
2000

出力例 3

0
0

  • 最大値の前後に値がないかもしれない.

入力例 4

10
9 12 30 63 55 8 10 1 27 13

出力例 4

51
114