Problem I. Market place ≡

Statement

A market has a line of N trading posts selling sunflower seeds. Prospective buyers walk along the line, then at some moment stop and buy the seeds to nibble. Quality of the seeds does not differ substantially among the posts, so the only difference is in price and location of posts. Before trying to enter this market as another seed seller, you have conducted a market research to find out how is the number of buyers influenced by these two factors. The research shows that most buyers follow the same pattern. They walk past some posts noticing and remembering the prices, then after passing K posts return to the one with the lowest price encountered, and make a purchase there, then leave the market. If there are several posts with the equal price, they choose the nearest one in the line. For example, let us assume there are five posts with prices 37, 34, 34, 35, 33. If the buyer with K = 4 walks from the left to right, he sees seeds priced at 37, 34, 34, 35. At this moment, he decides he has seen enough, and goes back to the third post and buys seeds there. Although the second post has the same price as the third, it is a longer walk for the buyer to return there. If the same buyer would enter the line from the right end, he would see prices 33, 35, 34, 34, then stop and return to the fifth post. The number of posts passed before the decision (K) is a function of buyer's greed and patience, and is obviously different for different buyers. The research yielded the average percentage B_K of buyers for all values of K.

You are to determine the optimal market strategy (i. e. the price and location of the new post which maximizes anticipated average income) under the assumptions that half of the clients walk in the direction from the first post to the Nth and another half - from the Nth post, to the first, and that they behave according to the pattern above.

Input file format

Output file format

Constraints

Sample tests

5
37 34 34 35 33
10 20 30 30 10

3 33