No.2053 12345...
タグ : / 解いたユーザー数 122
作問者 :
PCTprobability
/ テスター :
butsurizuki
Problem Statement
You are given a sequence of positive integers $A_1,A_2,\dots,A_N$ of length $N$.
Find the number of contiguous subarrays of $A$ of length at least $2$ that are arithmetic progressions with common difference $1$.
Constraints
- $2 \le N \le 2 \times 10^5$
- $1 \le A_i \le 10^9$
- $A_{i+1} \neq A_i - 1 \ (1 \le i \le N-1)$
- All input values are integers.
Input
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Output the answer.
Sample
Sample 1
Input
5 2 3 4 1 1
Output
3
The contiguous subarray $(2,3,4)$ consisting of the $1$-st through $3$-rd elements is an arithmetic progression with common difference $1$, so it satisfies the condition.
The contiguous subarray $(3,4,1)$ consisting of the $2$-nd through $4$-th elements is not an arithmetic progression, so it does not satisfy the condition.
The contiguous subarray $(4)$ consisting of the $3$-rd through $3$-rd elements does not have length at least $2$, so it does not satisfy the condition.
Sample 2
Input
10 1 2 3 4 5 6 7 8 9 10
Output
45
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。