Pairs Having Similar Elements
Tag(s):

## Arrays, Data Structures, Easy, One-dimensional

Problem
Editorial
Analytics

Given an array, $A$, having $N$ integers $A_1,A_2,...,A_N$.Two elements of the array $A_i$ and $A_j$ are called similar iff $A_i = A_j+1$ or $A_j = A_i + 1$ .
Also, the similarity follows transitivity. If $A_i$ and $A_j$ are similar and $A_j$ and $A_k$ are similar, then $A_i$ and $A_k$ are also similar.
Note: $i$, $j$, and $k$ are all distinct.

You need to find number of pairs of indices $(i,j)$ such that $i<j$ and $A_i$ is similar to $A_j$.

Input

The first line contains a single integer $N$ denoting number of elements in the array.
The second line contains $N$ space separated integers where $i^{th}$ elements indicate$A_i$.

Output

Output the number of pairs of indices $(i,j)$ such that $i<j$ and $A_i$ is similar to $A_j$ in a single line.

Constraints

$1 \le N \le 10^6\\ 10^{-9} \le A_i \le 10^9$

SAMPLE INPUT
8
1 3 5 7 8 2 5 7
SAMPLE OUTPUT
6

Explanation

We have $6$ possible pairs of indices which contain similar elements.
$(1,6)$ : $A_1$ and $A_6$ are similar since $2 = 1 + 1$.
$(2,6)$ : $A_2$ and $A_6$ are similar since $3= 2+1$.
$(1,2)$ : $A_1$ and $A_6$ are similar by transitivity since $(A_1,A_6)$ and $(A_2,A_6 )$ are similar, so $A_1$ and $A_2$ are also similar.
$(4,5)$ : $A_4$ and $A_5$ are similar since $8 = 7+1$.
$(5,8)$ : $A_5$ and $A_8$ are similar since $8= 7+1$
$(4,8)$ : $A_4$ and $A_8$ are similar by transitivity since $(A_4,A_5)$, $(A_5,A_8)$ are similar, so $A_4$ and $A_8$ are also similar.

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

Bosch DevOps Hiring challenge

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures