implicit none
integer(8):: i,j,k,n
integer(8),allocatable,dimension(:):: height,count,count_a
 
read (5,*) n
allocate(height(n))
allocate(count(n))
allocate(count_a(n))
count=0
count_a=0

do i=1,n
  read(5,*) height(i)
enddo
 
do i=1,n
j=i
k=n-i+1

    do while (j>=1)
        j=j-1
        if (height(i)>=height(j) .and. j>=1 .and.  j/=i) then

            if(count(j)==0) then
                count(i)=count(i)+1
            else 
                count(i)=count(i)+count(j)
                j=j-count(j)+1
            endif

        else if  (height(i)<height(j) .and. j>=1 .and.  j/=i) then
            exit
        endif
    enddo


    do while (k<=n)
        k=k+1
        if (height(n-i+1)>=height(k)  .and. k<=n .and.  k/=n-i+1) then

            if(count_a(k)==0) then
                count_a(n-i+1)=count_a(n-i+1)+1
            else 
                count_a(n-i+1)=count_a(n-i+1)+count_a(k)
                k=k+count_a(k)-1
            endif

        else if  (height(n-i+1)<height(k) .and. k<=n .and.  k/=n-i+1) then
            exit
        endif
    enddo

enddo

do i=1,n
write(6,"(i0)") count(i)+count_a(i)
enddo

stop
end