Shil and Wave seqeunce

★★★★★

4.5

36 votes

Approved, Bit Manipulation, Data Structures, Dynamic Programming, Medium, Open, Ready

Details

Submissions

Discussion

Editorial

Problem

Given a sequence A₁ , A₂ , A₃ .. A_N of length N . Find total number of wave subsequences having length greater than 1.
Wave subsequence of sequence A₁ , A₂ , A₃ .. A_N is defined as a set of integers i₁ , i₂ .. i_k such that A_i1 < A_i2 > A_i3 < A_i4 .... or A_i1 > A_i2 < A_i3 > A_i4 .... and i₁ < i₂ < ...< i_k.Two subsequences i₁ , i₂ .. i_k and j₁ , j₂ .. j_m are considered different if k != m or there exists some index l such that i_l ! = j_l

INPUT:
First line of input consists of integer N denoting total length of sequence.Next line consists of N integers A₁ , A₂ , A₃ .. A_N .

OUTPUT:
Output total number of wave subsequences of given sequence . Since answer can be large, output it modulo 10⁹+7

CONSTRAINTS:
1 ≤ N ≤ 10⁵
1 ≤ A_i ≤ 10⁵

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

All the possible sequences are: [ 1 3 ] , [1 5 ] , [ 1 4 ] , [1 2 ] , [1 3 2] , [1 4 2 ] , [1 5 2] , [1 5 4] , [3 5] , [3 4] , [3 2] , [3 5 2] , [3 4 2] , [3 5 4] , [5 4] , [5 2 ] , [4 2] . Note that value in the bracket are the values from the original sequence whose positions are maintained.