Vim으로 괄호 사이 커서 옮기기

시간 제한5초메모리 제한1024 MB

요약

괄호 문자열에서 h와 l은 1번, %는 2번으로 셀 때, 각 질의의 두 커서 위치 사이 최소 키 입력 수를 구합니다.

문제

현민이는 최근 프로그램 하나의 버그를 찾아 달라는 의뢰를 받았다. 의뢰자로부터 프로그램의 소스 코드와 개발용 노트북을 전달받은 현민이는 깜짝 놀라고 말았다.

첫 번째로 놀란 것은 코드의 생김새였다. 현민이가 받은 코드는 (, ), . 세 종류의 문자로만 이루어진 한 줄짜리 코드였다. 코드에서 . 문자를 모두 제거한 문자열은 올바른 괄호 문자열이었다.

두 번째로 놀란 것은 노트북에 깔려 있는 텍스트 에디터였다. 이 노트북에는 Vim밖에 깔려 있지 않았다. Vim에는 다양한 단축키가 있다고 알려져 있지만, 현민이가 아는 단축키는 세 개뿐이다.

h: 커서를 왼쪽으로 한 칸 움직인다. 이미 현재 줄의 가장 왼쪽에 있으면 움직이지 않는다.
l: 커서를 오른쪽으로 한 칸 움직인다. 이미 현재 줄의 가장 오른쪽에 있으면 움직이지 않는다.
%: 현재 커서 위치에 괄호 문자가 있을 때 그와 매칭되는 괄호가 있는 위치로 움직인다. 현재 위치에 괄호 문자가 없으면 움직이지 않는다. 현민이가 받은 코드는 올바른 괄호 문자열이므로 매칭되는 괄호가 없는 경우는 고려하지 않는다. %는 Shift + 5로 입력하므로 키를 두 번 누르는 것으로 센다.

디버깅을 하려면 커서를 아주 많이 움직여야 하므로, 최대한 효율적으로 키를 누르지 않으면 현민이의 손가락이 무사하지 못할 것이다. 현민이가 현재 커서의 위치와 목표 위치를 말해 줄 때마다, 커서를 목표 위치까지 옮기는 데 필요한 키 누름 횟수의 최솟값을 구하라.

첫 줄에 코드의 길이를 의미하는 정수 $N$ 과 질문의 개수를 의미하는 정수 $Q$ ( $1 \le N, Q \le 300,000$ )가 주어진다.

두 번째 줄에 코드를 의미하는 $N$ 글자의 문자열이 주어진다. 문자열은 공백을 포함하지 않으며 문제 내용의 조건을 만족한다.

다음 $Q$ 개의 줄에 걸쳐 각 줄에 각 질문의 현재 커서의 위치와 목표 위치를 나타내는 정수 $s$ , $e$ ( $1 \le s, e \le N$ )가 공백 하나를 사이에 두고 주어진다.

$Q$ 개의 줄에 걸쳐 각 줄에 각 질문에 대해 커서를 목표 위치까지 옮기는 데 필요한 최소 키 누름 횟수를 출력한다.