P6854 Tram

The tram set off, and its sound lingered in my mind: “Stay, come with me.” I turned back to look at the station, and it was gone. I searched for it on Des Voeux Road. There were not many passers-by, but it still disappeared. I pulled down the window, and the breeze gently brushed my face. Where did it go? Passers-by, streets, and towering buildings. They quietly flowed past me.

You are about to debut. Your coach and classmates have contacted a photographer for you, and you come to take promotional photos by Des Voeux Road. There are $n$ buildings on the street, arranged in a line from left to right, numbered from $1$ to $n$. The height of building $i$ is $a_i$. A photo can be described by an ordered pair $(l,r)$, where $1\le l\le r\le n$. This photo contains all buildings with indices in $[l,r]$. The photographer thinks a photo is beautiful if and only if it satisfies both conditions below: - For any $i

The first line contains a positive integer $n$, representing the number of buildings. The next line contains $n$ positive integers. The $i$-th integer is the height of building $i$.

Output one line containing one integer, representing the number of different beautiful photos that can be taken.

**This problem uses bundled tests.** You can get the score for a subtask only if you pass all test points in that subtask. - Subtask 1 (10 points): $n\le 200$. - Subtask 2 (5 points): $n\le 1000$. - Subtask 3 (10 points): $n\le 6000$. - Subtask 4 (20 points): $n\le 3\times 10^4$. - Subtask 5 (30 points): $n\le 10^5$. - Subtask 6 (25 points): $n\le 10^6$. For all testdata: $1\le n,a_i\le 10^6$. Note that the answer may exceed the range of a $32$-bit signed integer. The input size is large, so please use a fast input method. Translated by ChatGPT 5