Close Subsequences
Tag(s):

## Algorithms, Dynamic Programming, Dynamic programming, Easy-Medium, dp

Problem
Editorial
Analytics

Given an array $A$ , a subsequence of A is said to be good subsequence, if it has at least one pair of consecutive elements such that their absolute difference is less than equal to 1.

Formally, if the subsequence $B$ has $m$ elements, then it is a good subsequence if there exists at least one index $i$ ($2 \le i \le m$) such that $abs(B_i - B_{i-1}) \le 1$.

You have to find the total number of good subsequences of array A modulo $10^9+7$.

Obviously, a good subsequence has to have at least 2 elements in it.

For example if sequence has 3 elements [3, 4, 5], subsequence [3, 4], [4, 5] and [3, 4, 5] are good subsequnces. So our answer will be 3 in this case.

Input Format

The first line contains a single integer $N$ ($2 \le n \le 10^5$), denoting the number of elements in A

The second line contains $N$ integers $A_1, A_2, \ldots, A_n$ ($1 \le A_i \le 10^5$).

Output Format

Output the total number of good subsequences of the array $A$ modulo $10^9$+7

SAMPLE INPUT
5
1 6 2 1 9

SAMPLE OUTPUT
12

Explanation

[1, 2], [1, 2, 1], [1, 2, 1, 9], etc. are some of the good subsequences. Total 12 are there in the given sample.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in Challenge Name

May Easy' 19

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Python > Getting Started
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures