오름차순으로 정렬된 서로 다른 정수 \(N\)개가 주어진다. 배열에서 정수 \(X\)를 순차 탐색과 이분 탐색으로 각각 찾아보려고 한다.

순차 탐색은 배열의 첫 번째 원소부터 차례대로 \(X\)와 비교한다. \(X\)를 발견하면 탐색을 종료하며, 배열의 모든 원소를 확인할 때까지 발견하지 못하면 탐색에 실패한다.

이분 탐색은 현재 탐색 구간의 가운데 원소를 \(X\)와 비교한다. 가운데 원소가 \(X\)보다 작으면 오른쪽 구간을 탐색하고, \(X\)보다 크면 왼쪽 구간을 탐색한다. 탐색 구간의 양 끝은 모두 포함하며, 가운데 위치가 두 곳이라면 왼쪽 위치를 선택한다.

한 번의 비교는 배열의 원소 하나와 \(X\)를 비교하는 것을 뜻한다. 하나의 원소를 확인하는 과정에서 여러 조건문을 사용하더라도 비교 횟수는 한 번만 증가한다.

예를 들어 다음과 같은 배열과 \(X\)가 있다고 하자.

\(A=[2,5,8,12,16,23,38,56,72]\), \(X=23\)

순차 탐색의 비교 과정은 다음과 같다.

따라서 순차 탐색의 비교 횟수는 \(6\)이다.

이분 탐색의 비교 과정은 다음과 같다.

따라서 이분 탐색의 비교 횟수는 \(3\)이다.

주어진 배열에서 \(X\)를 순차 탐색했을 때의 비교 횟수와 이분 탐색했을 때의 비교 횟수를 각각 구하여라.

입력

첫째 줄에 배열의 원소 개수 \(N\)이 주어진다.

둘째 줄에 서로 다른 정수 \(A_1,A_2,\ldots,A_N\)이 공백으로 구분되어 주어진다. 배열은 오름차순으로 정렬되어 있다.

셋째 줄에 찾으려는 정수 \(X\)가 주어진다.

• \(1\le N\le1,000,000\)
• \(-1,000,000,000\le A_i\le1,000,000,000\)
• \(A_i<A_{i+1}\) \((1\le i<N)\)
• \(-1,000,000,000\le X\le1,000,000,000\)
• \(X\)는 배열에 존재하지 않을 수도 있다.

출력

순차 탐색으로 \(X\)를 찾을 때의 비교 횟수와 이분 탐색으로 \(X\)를 찾을 때의 비교 횟수를 공백으로 구분하여 출력한다.

예제 입력 1

9
2 5 8 12 16 23 38 56 72
23

예제 출력 1

6 3

예제 입력 2

8
1 4 7 10 13 16 19 22
15

예제 출력 2

8 3

두 번째 예제에서 \(15\)는 배열에 존재하지 않는다. 순차 탐색은 모든 원소를 확인하며, 이분 탐색은 \(10\), \(16\), \(13\)을 차례대로 확인한 뒤 탐색을 종료한다.