{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe Smart Beaver from ABBYY started cooperating with the Ministry of Defence. Now they train soldiers to move armoured columns. The training involves testing a new type of tanks that can transmit information. To test the new type of tanks, the training has a special exercise, its essence is as follows.\u003c/p\u003e\u003cp\u003eInitially, the column consists of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e tanks sequentially numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e in the order of position in the column from its beginning to its end. During the whole exercise, exactly \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e messages must be transferred from the beginning of the column to its end.\u003c/p\u003e\u003cp\u003eTransferring one message is as follows. The tank that goes first in the column transmits the message to some tank in the column. The tank which received the message sends it further down the column. The process is continued until the last tank receives the message. It is possible that not all tanks in the column will receive the message — it is important that the last tank in the column should receive the message.\u003c/p\u003e\u003cp\u003eAfter the last tank (tank number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e) receives the message, it moves to the beginning of the column and sends another message to the end of the column in the same manner. When the message reaches the last tank (tank number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e), that tank moves to the beginning of the column and sends the next message to the end of the column, and so on. Thus, the exercise is completed when the tanks in the column return to their original order, that is, immediately after tank number \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e moves to the beginning of the column.\u003c/p\u003e\u003cp\u003eIf the tanks were initially placed in the column in the order \u003cspan class\u003d\"tex-span\"\u003e1, 2, ..., \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, then after the first message their order changes to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e, 1, ..., \u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e, after the second message it changes to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1, \u003ci\u003en\u003c/i\u003e, 1, ..., \u003ci\u003en\u003c/i\u003e - 2\u003c/span\u003e, and so on.\u003c/p\u003e\u003cp\u003eThe tanks are constructed in a very peculiar way. The tank with number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e is characterized by one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, which is called the \u003cspan class\u003d\"tex-font-style-underline\"\u003emessage receiving radius\u003c/span\u003e of this tank.\u003c/p\u003e\u003cp\u003eTransferring a message between two tanks takes one second, however, not always one tank can transmit a message to another one. Let\u0027s consider two tanks in the column such that the first of them is the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th in the column counting from the beginning, and the second one is the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e-th in the column, and suppose the second tank has number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e. Then the first tank can transmit a message to the second tank if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e \u0026lt; \u003ci\u003ej\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e ≥ \u003ci\u003ej\u003c/i\u003e - \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe Ministry of Defense (and soon the Smart Beaver) faced the question of how to organize the training efficiently. The exercise should be finished as quickly as possible. We\u0027ll neglect the time that the tanks spend on moving along the column, since improving the tanks\u0027 speed is not a priority for this training.\u003c/p\u003e\u003cp\u003eYou are given the number of tanks, as well as the message receiving radii of all tanks. You must help the Smart Beaver and organize the transferring of messages in a way that makes the total transmission time of all messages as small as possible.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e — the number of tanks in the column. Each of the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 250000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — the message receiving radii of the tanks in the order from tank \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to tank \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (let us remind you that initially the tanks are located in the column in ascending order of their numbers).\u003c/p\u003e\u003cp\u003eTo get the full points for the first group of tests it is sufficient to solve the problem with \u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 300\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTo get the full points for the second group of tests it is sufficient to solve the problem with \u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10000\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTo get the full points for the third group of tests it is sufficient to solve the problem with \u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 250000\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint a single integer — the minimum possible total time of transmitting the messages.\u003c/p\u003e\u003cp\u003ePlease, do not use the \u003cspan class\u003d\"tex-font-style-tt\"\u003e%lld\u003c/span\u003e specifier to read or write 64-bit integers in С++. It is preferred to use the \u003cspan class\u003d\"tex-font-style-tt\"\u003ecin\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003ecout\u003c/span\u003e streams or the \u003cspan class\u003d\"tex-font-style-tt\"\u003e%I64d\u003c/span\u003e specifier.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n2\n2\n2\n2\n2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample the original order of tanks is \u003cspan class\u003d\"tex-span\"\u003e1, 2, 3\u003c/span\u003e. The first tank sends a message to the second one, then the second tank sends it to the third one — it takes two seconds. The third tank moves to the beginning of the column and the order of tanks now is \u003cspan class\u003d\"tex-span\"\u003e3, 1, 2\u003c/span\u003e. The third tank sends a message to the first one, then the first one sends it to the second one — it takes two more seconds. The second tank moves to the beginning and the order of the tanks is now \u003cspan class\u003d\"tex-span\"\u003e2, 3, 1\u003c/span\u003e. With this arrangement, the second tank can immediately send a message to the first one, since the message receiving radius of the first tank is large enough — it takes one second. Finally, the tanks return to their original order \u003cspan class\u003d\"tex-span\"\u003e1, 2, 3\u003c/span\u003e. In total, the exercise takes \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e seconds.\u003c/p\u003e\u003cp\u003eIn the second sample, all five tanks are the same and sending a single message takes two seconds, so in total the exercise takes \u003cspan class\u003d\"tex-span\"\u003e10\u003c/span\u003e seconds.\u003c/p\u003e"}}]}