Problem G: 掐头去尾 / Delete and Backspace
Memory Limit：128 MB
Time Limit：1.000 S
Submit：6
Solved：4
Description
给定一个长度为几的数组 a。对于每个k=1,2,...,n，独立地考虑以下过程。
初始时，数组为 a。你需要恰好进行k次操作。每次操作可以选择以下两种方式之一:
Backspace:删除当前数组的第一个元素
Delete:删除当前数组的最后一个元素。
你的得分定义为第k次操作中被删除元素的值。
对于每个k=1,2,...,n，求你能够获得的最大得分。
Input
第一行包含一个整数 n，表示数组的长度(1 <n < 105)。
第二行包含几 个整数 a1, a2,...,an，表示数组 a(1 ≤ ai< 109)。
第二行包含几 个整数 a1, a2,...,an，表示数组 a(1 ≤ ai< 109)。
Output
输出几个整数。其中，第k个整数表示恰好进行 n 次操作时能够获得的最大得分。
Sample Input Copy
5
2 7 8 1 4Sample Output Copy
4 7 8 8 8HINT
对于 k=1，只能删除数组最左边的 2 或最右边的 4，因此最大得分为 4。
对于 k=2，可以第一次删除最左边的 2，第二次再删除最左边的 7，此时第二次操作删除的元素为 7，因此最大得分为 7。
对于 k=3，可以依次删除最左边的 2,7,8，使第三次操作删除的元素为 8，因此最大得分为 8。
对于 k=4 和 k=5，同样可以合理安排前面的操作，使最后一次操作删除的元素为 8。