문제 설명

봉인을 모두 풀어낸 일행은 마침내 왕좌의 대청에 들어섰습니다. 사자 왕의 포효 한 번에 신하들이 벌벌 떨던 바로 그곳입니다. 둥근 대청 둘레에는 높이가 제각각인 기둥이 원을 그리며 서 있고, 기둥 꼭대기마다 봉화대가 놓여 있습니다.
뮤라가 작전을 설명했습니다.
"기둥마다 한 명씩 올라가 봉화를 켜. 서로 보이는 봉화끼리 신호를 주고받으면, 라이언 타운 밖에서 기다리는 평민들에게까지 한꺼번에 알릴 수 있어."
"그럼 서로 보이는 봉화가 몇 쌍인지부터 세야 한다 개굴."
"기둥이 이렇게 많은데 한 쌍씩 다 따져 보다간 해가 진다냥!"
기둥은 n개이고, 원을 따라 차례로 0번부터 n-1번까지 번호가 붙어 있습니다. n-1번 기둥과 0번 기둥도 서로 이웃합니다. data[i]는 i번 기둥의 높이입니다.
서로 다른 두 기둥 사이에는 원을 따라 가는 두 갈래 길(원호)이 있습니다. 두 원호 가운데 어느 한쪽에라도 두 기둥 중 낮은 쪽보다 더 높은 기둥이 하나도 없으면, 두 기둥의 봉화는 서로 보입니다.
- 두 기둥 자신은 원호에 넣지 않습니다. 원호 위에 기둥이 하나도 없으면(두 기둥이 이웃하면) 언제나 서로 보입니다.
- 낮은 쪽과 높이가 같은 기둥은 시야를 가리지 않습니다.
- 기둥이 2개면 두 기둥은 서로 이웃하므로 서로 보이는 쌍은 1개입니다. 기둥이 1개면 0개입니다.
서로 보이는 봉화 쌍의 수를 return 하세요. 두 기둥 (a, b)와 (b, a)는 같은 쌍으로 한 번만 셉니다.
제한 사항
- n(
data의 길이)은 1 이상 100,000 이하입니다. - 기둥의 높이는 1 이상 1,000,000,000 이하의 정수입니다.
- 답이 int 범위를 넘을 수 있습니다.
입출력 예
| 입력 | 출력 |
|---|---|
| [5, 3, 4, 1, 2] | 7 |
| [2, 2, 2, 2] | 6 |
| [4, 1, 4, 1, 4, 1] | 9 |
입출력 설명
입출력 예 #1
- 이웃한 기둥 5쌍(0-1, 1-2, 2-3, 3-4, 4-0)은 언제나 서로 보입니다.
- 0번(높이 5)과 2번(높이 4): 사이에 있는 1번(높이 3)이 낮은 쪽 높이 4보다 높지 않아 서로 보입니다.
- 2번(높이 4)과 4번(높이 2): 사이에 있는 3번(높이 1)이 2보다 높지 않아 서로 보입니다.
- 0번과 3번(높이 1)은 한쪽 원호에 1번·2번(높이 3, 4), 다른 쪽 원호에 4번(높이 2)이 있어 양쪽 모두 막힙니다. 1번과 3번, 1번과 4번도 양쪽 원호가 모두 막힙니다.
서로 보이는 쌍은 5 + 2 = 7개입니다.
입출력 예 #2
높이가 같은 기둥은 시야를 가리지 않으므로, 4개 기둥에서 만들 수 있는 6쌍이 모두 서로 보입니다.
입출력 예 #3
이웃한 6쌍은 서로 보입니다. 높이 4인 0번·2번·4번은 어느 두 기둥을 골라도 한쪽 원호에 높이 1인 기둥 하나만 있어서 서로 보입니다(3쌍). 높이 1인 기둥끼리는 양쪽 원호 모두 높이 4인 기둥에 막힙니다. 모두 9쌍입니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | [5, 3, 4, 1, 2] | 7 |
| 2 | [2, 2, 2, 2] | 6 |
| 3 | [4, 1, 4, 1, 4, 1] | 9 |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 15개도 함께 채점해요.