When you're a princess, you get to see a lot of frogs throughout the day and have to kiss one of them. But you can see only one frog at a time, and once you reject a frog you can't return to it. However, as soon as you kiss a frog, you're stuck with that prince for the rest of your life. So, how can you know when to stop hoping for the frog prince of your dreams and settle down with the frog you hold in your hands?

Gabor Szekely writes in Paradoxes in Probability Theory and Mathematical Statistics (1986):

"Surprisingly, there is a method which enables you to select the most handsome frog out of the $n$ frogs with a probability of nearly 37% even if $n$ is large, under the condition that you can see only one frog at a time, can only kiss a single frog and have to decide immediately whether or not to kiss the frog."

This is achieved using the following strategy. When you get to see a frog, you give it a rating $s \in \mathbb{R}$ ($0 \leq s \leq 1$) that indicates how handsome the frog is. The higher the rating, the more handsome you value the frog. Let the first $\left\lceil \frac{n}{e} \right\rceil$ frogs go and then select the first one that has a higher rating than any previous candidate. If none are better, you have to kiss the last frog no matter how ugly or beautiful it is.

This strategy will give you a $\frac{1}{e} \approx 37\%$ chance to kiss the frog with the highest rating, no matter how large $n$ is. For example, assume there are 14 frogs in a forest. In that case, you only rate the first $\left\lceil \frac{14}{e} \right\rceil = \left\lceil 5.15 \right\rceil = 6$ frogs without kissing them. You then kiss the first frog having a higher rating than all of the first 6 frogs.

Input

The first line of the input contains a number $n \in \mathbb{N}$ ($8 \leq n \leq 40$) that indicates how many frogs there are. This is followed by the ratings $s \in \mathbb{R}$ ($0 \leq s \leq 1$) that are assigned to the $n$ frogs, each on a separate line.

Output

The rating $s$ of the frog that will be kissed by the princess, if she follows the strategy as outline above.

Example

Input:

14
0.0056
0.7911
0.4679
0.3439
0.5503
0.5688
0.3085
0.9156
0.5654
0.2818
0.1636
0.4068
0.9669
0.1147

Output:

0.9156

Epilogue

One day a young man was walking down a road when a frog called to him: "Boy, if you kiss me, I will turn into a beautiful princess." The young man picked up the frog, smiled at it and put it in his pocket.

A short while later, the frog said, "Boy, if you kiss me and turn me back into a beautiful princess, I'll be yours." The young man took the frog from his pocket, smiled at it and put it back.

Now the frog was upset. "Boy, what is the matter?" the frog cried. "I have told you that I am a beautiful princess, and if you kiss me, I'll be yours!" The young man took the frog from his pocket, looked at it and said: "Look, I'm an engineer. I have no time for a girlfriend, but a talking frog is cool!"

Bronnen

• Gaither CC (1999). Practically speaking: a dictionary of quotations on engineering, technology and architecture. CRC Press.

Als prinses krijg je de godganse dag kikkers te zien, waarvan je er uiteindelijk één moet kussen. Je ziet slechts één kikker tegelijkertijd en als je weigert om die te kussen dan krijg je hem nooit meer opnieuw te zien. Kus je de kikker wel, dan zit je voor eeuwig en altijd met die prins opgescheept. Maar hoe kan je weten wanneer je de hoop moet opgeven om de kikkerprins van je dromen tegen te komen, en best tevreden bent met de kikker die je in je handen hebt?

Gabor Szeleky schrijft hierover in Paradoxes in Probability Theory and Mathematical Statistics (1986):

"Verrassend genoeg is er een methode die ongeveer 37% kans oplevert om uit een reeks van $n$ kikkers de knapste kikkerprins te kussen, als je de kikkers één voor één te zien krijgt, je slechts één kikker mag kussen, en je onmiddellijk moet beslissen of je de kikker die je voor je ziet kust of niet."

Hiervoor moet je uitgaan van de volgende strategie. Telkens je een kikker te zien krijgt, geef je hem een score $s \in \mathbb{R}$ ($0 \leq s \leq 1$) die aangeeft hoe knap de kikker is. Hoe hoger de score, hoe knapper je de kikker vindt. De eerste $\lceil \frac{n}{e} \rceil$ kikkers kus je niet, maar je onthoudt wel de hoogste score die je aan die kikkers hebt gegeven. Daarna kus je de eerstvolgende kikker die een hogere score heeft dan de hoogste score van de eerste $\left\lceil \frac{n}{e} \right\rceil$ kikkers. Als je de laatste kikker te zien krijgt, dan moet je die wel kussen ongeacht hoe mooi of lelijk je hem vindt.

Deze strategie geeft je $\frac{1}{e} \approx 37\%$ kans om de kikker met de hoogste score te kussen, ongeacht hoe groot $n$ is. Als er bijvoorbeeld 14 kikkers in het bos zitten, dan negeer je de eerste $\left\lceil \frac{14}{e} \right\rceil = \left\lceil 5.15 \right\rceil = 6$ kikkers, en kus je de eerstvolgende kikker die een hogere score heeft dan elk van de eerste 6 kikkers.

Invoer

De eerste regel van de invoer bevat een getal $n \in \mathbb{N}$ ($8 \leq n \leq 40$) dat aangeeft hoeveel kikkers er zijn. Daarna volgen de scores $s \in \mathbb{R}$ ($0 \leq s \leq 1$) die aan de $n$ kikkers gegeven worden, elk op een afzonderlijke regel.

Uitvoer

De score $s$ van de kikker die uiteindelijk door de princes zal gekust worden, als ze de strategie volgt die hierboven staat beschreven.

Voorbeeld

Invoer:

14
0.0056
0.7911
0.4679
0.3439
0.5503
0.5688
0.3085
0.9156
0.5654
0.2818
0.1636
0.4068
0.9669
0.1147

Uitvoer:

0.9156

Epiloog

Op een zekere dag liep een jongeman langs de weg toen hij plots werd aangesproken door een kikvors: "Jongen, als je me kust, dan verander ik in een beeldschone prinses." De jongeman raapte de kikvors op, lachte ernaar en stopte haar in zijn broekzak.

Een poosje later zei de kikvors, "Jongen, als je me kust en me in een beeldschone prinses verandert, dan mag je met me trouwen." De jongeman nam de kikvors uit zijn broekzak, lachte ernaar en stopte hem daarna terug.

Nu begon de kikvors zich echt boos te maken. "Jongen, wat is er aan de hand?" riep de kikvors. "Ik heb je gezegd dat ik een beeldschone prinses bent, en dat je met me mag trouwen als je me kust!" De jongeman nam de kikvors uit zijn broekzak en zei: "Kijk, ik ben een ingenieur. Ik heb geen tijd voor een vriending, maar een pratende kikvors vind ik cool!"

Bronnen

• Gaither CC (1999). Practically speaking: a dictionary of quotations on engineering, technology and architecture. CRC Press.