오아시스 재결합
시간 제한1초메모리 제한256 MB
줄지어 선 사람들의 키가 주어질 때, 단조 스택으로 서로 볼 수 있는 쌍의 수를 세되 같은 키인 경우를 올바르게 처리해야 합니다.
문제
오아시스의 재결합 공연을 보기 위해 N명이 한 줄로 서 있다.
두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 있는 모든 사람의 키가 A와 B 중 더 작은 키보다 크지 않아야 한다. 키가 같은 사람은 서로의 시야를 막지 않는다.
줄에 선 순서대로 각 사람의 키가 주어질 때, 서로 볼 수 있는 사람 쌍의 수를 구하라.
입력
첫째 줄에 줄에 서 있는 사람의 수 N이 주어진다. (1 <= N <= 500,000)
둘째 줄부터 N개의 줄에는 사람들이 서 있는 순서대로 각 사람의 키가 나노미터 단위로 주어진다. 모든 키는 2^31 나노미터보다 작다.
출력
서로 볼 수 있는 사람 쌍의 수를 출력한다.