No.3371 Add Insert Operations
レベル :
/ AI推定難易度 : 2400
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 :
rhoo
/ テスター :
Naru820
jupiter_68
noya2
タグ : / 解いたユーザー数 15
作問者 :
noya2
問題文最終更新日: 2025-11-17 12:18:55
English (AI translation)
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence.
Back to the original
Problem Statement
Consider the following operation on a sequence.
- Choose any position in the sequence and insert $0$ there. Then, if a number exists immediately to the left of the inserted position, add $1$ to that number, and similarly, if a number exists immediately to the right of the inserted position, add $1$ to that number.
Here, two ways of performing the operations are considered different if the numbers of operations differ, or if for some $i$ the insertion positions of the $i$-th operation differ.
Constraints
- $1 \le N \le 2 \times 10^5$
- $0 \le A_i \le 10^9$
- All input values are integers.
Input
The input is given from standard input in the following format.
$N$ $A_1\; A_2\; \dots\; A_N$
Output
Output the answer in $1$ line.
Sample
Sample 1
Input
3 0 2 0
Output
2
If you insert at the far left in the $1$-st operation and at the far right in the $2$-nd operation, the sequence changes as $0\;\to\; 0,1\;\to\; 0,2,0$.
Sample 2
Input
2 0 0
Output
0
There is no way of performing the operations such that the sequence finally becomes $0,\; 0$.
Sample 3
Input
20 1 0 5 0 1 1 4 2 0 2 0 7 0 1 1 2 0 5 0 2
Output
454727167
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。