Beautiful Prefix Sequences

3.2

5 votes
Algorithms, Datastructures, Segment tree, Dynamic Programming, Stack
Problem

A sequence of integers x1,x2,,xN is called beautiful if it can be split into contiguous subsequences such that

  • Each subsequence consists of at least 3 elements
  • xi<xl and xi<xr for every i(l<i<r) in contiguous subsequence xl,xl+1,,xr1,xr.

For instance 7, 5, 3, 2, 6, 4, 1, 3, 5 is a beautiful sequence which can be split into [7,5,3,2,6] [4,1,3,5], but 7, 5, 3, 2, 4, 1, 3, 5 is not a beautiful sequence.

Given a sequence A1,A2,,AN. Emil decided to find out the number of indices i such that the prefix sequence A1,A2,,Ai is beautiful.  This task is too hard for him, so he asks you to help.

Find out the number of beautiful prefix sequences.

 Input format

  • The first line contains N denoting the length of the sequence.    
  • The ith of the next N lines contains Ai.

Output format

The count of beautiful prefix sequences.

Constraints

1N1051Ai105

Time Limit: 0.5
Memory Limit: 256
Source Limit:
Explanation

There are 2 beautiful prefix sequences [14,2,6],[14,2,6,3,9].

Editor Image

?