3764: make friends

According to the rules of BUCT, when we initiate new students on the first day, the monitor will organize class activities to enhance the friendship between classmates.Because the monitor prefers rectangles to circles，he asks all the students to sit in a rectangular shape. Each student has an energy value, and two students can be good friends if and only if the energy of all the students sitting between them is no higher than the energy of either of them. 
(A B C：A and C can be good friends if and only if Bi<=Ai and Bi<=Ci)
Obviously, two neighboring classmates can become good friends directly. There are two parts of the students clockwise and counterclockwise between A and B ,and as long as there is one situation that meets the requirements so that A and B can be good friends.
Because the monitor is busy buying presents for the students, he is going to give you n energies of students in turn now, and he wants to know how many pairs of students can be good friends. 

The first line contains one integer n (3 ≤ n ≤ 10^6) —— the total number of classmates
The second line contains n integers a1,a2,…,an (1 ≤ ai ≤ 10^9) —— student's energy in the clockwise direction

	



	

5
8 9 6 5 4

7