Énoncé¶

Dans ce problème, il vous est proposé de jouer au jeu des "fléchettes métriques". Sur un mur est affichée une série de $N$ nombres alignés de gauche à droite. Pour faire une partie, vous devez d'abord vous positionner à une certaine distance du mur, en face d'un élément de votre choix, puis tenter de lancer un certain nombre de fléchettes sur le mur afin d'obtenir le plus grand score possible.

Pour le positionnement, vous devez vous situer à une distance $d$ (en mètres) impaire du mur, en face d'un nombre en position $i$ de votre choix. Le premier nombre inscrit sur le mur aura comme position $i = 0$, le suivant $i = 1$ et ainsi de suite. Par exemple, vous pouvez vous placer à 1 mètre du mur en face du premier nombre, comme vous pouvez vous positionner à 7 mètres du mur en face du deuxième nombre.

Pour le lancer des fléchettes, on vous attribue $d$ fléchettes, c'est-à-dire un nombre de fléchettes égal à votre distance en mètres par rapport au mur. Par exemple, si vous vous êtes placé à un mètre du mur, vous disposez d'une seule fléchette, mais si vous vous êtes placé à 5 mètres du mur, vous disposez alors de cinq fléchettes. Vous lancez ensuite une à une la totalité des fléchettes à votre disposition.

Chaque fléchette se plantera de manière uniformément aléatoire dans une plage centrée sur la position $i$ et de longueur $d$. Par exemple, si vous vous situez à 3 mètres du mur, la fléchette peut finir avec une probabilité égale sur le nombre en face de vous, le nombre à sa gauche et le nombre à sa droite, soit une plage de $d=3$ nombres dont celui en face de vous (en position $i$) est l'élément central. Si vous vous êtes placé à 1 mètre du mur, votre fléchette tombera donc à coup sûr sur l'élément en face de vous. Si la plage s'étend en dehors du mur, il est possible que la fléchette rate le mur.

Le score d'une fléchette correspond au nombre touché par la fléchette. Si la fléchette n'atteint pas le mur, le score associé est de 0. Votre score correspond à la somme des scores des fléchettes envoyées.

Indiquez le positionnement, (c'est-à-dire la distance $d$ vous séparant du mur ainsi que la position $i$ du nombre en face de vous), maximisant l'espérance de votre score.

L'espérance du score peut se calculer en multipliant le score moyen par fléchette avec votre nombre de fléchettes.

Entrée¶

L’entrée contiendra :

• Sur la première ligne, un entier : N, La taille du mur.
• Sur la ligne suivante, une liste de N entiers séparés par des espaces : M, Le mur.

Sortie¶

Afficher sur la même ligne la distance $d$ et la position optimale $i$ à viser, séparées par un espace. Si plusieurs positions optimales existent, afficher la plus proche du mur. Si plusieurs solutions existent, afficher n'importe laquelle d'entre elles.

Contraintes¶

• $1 \le N \le 100\,000$
• $-1\,000\,000 \le M[ ] \le 1\,000\,000$