În Piatra Neamț sunt N+2 locații numerotate de la 0 la N+1, de la stânga la dreapta. Distanța dintre două locații i si j este egală cu |i – j|. La început, în locațiile 0 și N+1, sunt construite benzinării, și în celelalte locații sunt case. Compania BuildNT a decis sa construiască N benzinării, una în fața fiecărei case.

Înainte să construiască o benzinărie, constructorii calculează valoarea S egală cu suma distanțelor de la fiecare casă la cea mai apropiată benzinărie, si adaugă această sumă la suma totală T. După, ei aleg o casă, la cea mai mare distanță de orice benzinărie, în fața căreia construiesc o nouă benzinărie. Casele sunt alese în așa fel încât, după construirea benzinăriilor, valoarea S recalculată sa fie minimă. Dacă sunt mai multe case ce respectă această regulă, se alege prima din stânga.
Desigur, după ce toate benzinăriile au fost construite, suma S va deveni 0 și suma totală T nu se va mai schimba.

Cerința

Calculați T pentru o valoare dată N.

Date de intrare

Prima linie conține doar un număr N – numărul de case.

Date de ieșire

Scrieți un singur număr – suma totală T după ce toate cele N benzinării au fost construite.

Restricții și precizări

• 1 ≤ N ≤ 1 000 000 000
• Pentru 30% din cazuri N ≤ 10 000
• Pentru alte 30% din cazuri N ≤ 1 000 000

Exemplu:

Intrare

12

Ieșire

124

Explicație

In tabelul de mai jos este explicația pentru calcularea T când N=12.
Prima coloană conține distanța de la fiecare locație (incluzând locațiile 0 și N+1=13) la cele mai apropiate benzinării.

Distante pentru toate locațiile S T Locația unde se construiește o benzinărie
0 1 2 3 4 5 6 6 5 4 3 2 1 0 42 42 6
0 1 2 3 2 1 0 1 2 3 3 2 1 0 21 63 9
0 1 2 3 2 1 0 1 1 0 1 2 1 0 15 78 3
0 1 1 0 1 1 0 1 1 0 1 2 1 0 10 88 11
0 1 1 0 1 1 0 1 1 0 1 0 1 0 8 96 1
0 0 1 0 1 1 0 1 1 0 1 0 1 0 7 103 2
0 0 0 0 1 1 0 1 1 0 1 0 1 0 6 109 4
0 0 0 0 0 1 0 1 1 0 1 0 1 0 5 114 5
0 0 0 0 0 0 0 1 1 0 1 0 1 0 4 118 7
0 0 0 0 0 0 0 0 1 0 1 0 1 0 3 121 8
0 0 0 0 0 0 0 0 0 0 1 0 1 0 2 123 10
0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 124 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 124 Sfârșit