Description

Luchu在學校是個很受女同學歡迎的男生，在他要畢業的時候，學校將舉辦著一場盛大的舞會，大受歡迎的Luchu受到了眾多女性的舞伴邀請，Luchu想從這幾個女性挑出適合做為舞伴的女性。為了讓他能在畢業舞會中展現絕妙的舞姿，他決定由下列的方法選出最適合的女伴：

1. 這位女伴的身高不能跟自己一樣高，不然跳起來在視覺上太對稱會沒有美感
2. 因為Luchu不希望女伴和自己身高差太多，所以他打算從比他矮的女性中挑一個最高的作為女伴後選A
3. Luchu不在乎女伴比自己高，但也不能高太多，所以他打算從比他高的女性中挑一個最矮的作為女伴後選B

Luchu想先知道女伴後選A和B的身高後再決定要選哪位作為舞會的幸運兒。今天女同學由左到右，按照身高由低到高排列 (相鄰的兩位女同學的身高可以相等)，今天Luchu告訴你他自己的身高，想要問你女伴後選A, B的身高各是多少？

Input

輸入只有一組測試資料，第一行有一個數字N (1 <= N <= 50,000)，表示有N位想要跟Luchu跳舞的女同學。第二行是這N位女同學由小到大排列的身高，身高的範圍以正整數表示 (1~2³¹-1)，每個數字後面都會有一個空白隔開。第三行Q (1 <= Q <= 25,000)，表示Luchu有幾種可能的身高，不用為此感到奇怪，因為當Luchu發覺他適合的女伴後選A和B都不合他的胃口時，他會換一雙不同高度的鞋子來微調他的身高，直到他覺得滿意為止。) 下一行有Q個Luchu可能的身高，也是以正整數表示 (1~2³¹-1)，每個數字後面都會有一個空白隔開。

注意：輸入和輸出請不要使用C++的cin, cout，這兩個太慢可能會造成超時的問題，可以使用scanf和printf作為替代。

Output

輸出一共有Q行，每行都有兩個正整數，並且這兩個數字之間以一個空白隔開，每行的這兩個數字代表每次得到Luchu後，女伴候選A和B的身高，如果沒有比Luchu矮或高的女伴，就輸出大寫字母X表示。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

排序是一個很常被使用的工具，如何更有效率的完成排序是一件很重要的事情。

交換排序的程式，雖然可以很簡單的使用O(n²) 的演算法來完成，不過我們希望改善他的效率，

因此同樣的題目，我們把數字的個數提升到1000倍！

提示：Merge Sort可以解決這個問題

Input

輸入有多組測試資料。每組測試資料會給定一個N (N<=1,000,000)，代表有幾個數字。

下一行會有N個以空白隔開的整數，代表這N個數字。

輸入以EOF結束。

Output

對每組測試資料印出一行"Minimum exchange operations : M"，M是最少翻轉的次數。

注意：M可能會超過int範圍

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

畢業的季節要到了. 為了給他女朋友一個畢業禮物, 大衛霍夫曼決定打造一個金鍊子. 他收集了很多的金條並且打算送到打鐵店把他們通通連成一條. 而打鐵店很有個性的每次只能連接兩個金條, 而連起來的價錢就是兩個金條長度相加, ex:長度2和長度3的連接起來的價錢為5 大衛是個窮苦的學生, 所以他希望能夠讓組合的價錢越低越好, 身為好朋友的你, 能不能幫他算出最低的組合價錢呢？！

Input

第一行輸入一個整數T(<=20), 表示有幾組測試資料. 每組測試資料描述了大衛要買得鍊子資訊. 接下來每組會先輸入一個N(1<=N<=40000), 表示大衛要買得鍊子數量. 接下來N個數字L1, L2, ..., LN, 描述了這N個鍊子的長度.

Output

對每組測試資料, 印出一行大衛要花的最少價錢

Sample Input  Download

Sample Output  Download

Tags

Discuss