어떤 도시에 불고기 축제가 열린다. Ryu는 맛있는 요리를 만들기 위해서 요리 선생님 Han을 찾아갔다. Han이 Ryu에게 불고기 핫도그라는 요리를 만드는 데 필요한 재료들을 알려주었다. Han은 불확실한 것을 피하기 위해 정확한 논리식 형태로 설명해 주었다고 한다.

Han은 Ryu에게 마트에서 불고기 핫도그 재료를 정확하게 사오면 만드는 법을 알려주기로 했다. Ryu는 마트를 돌아다니면서 Han이 말한 재료를 장바구니에 담았다.

하지만 Ryu는 장바구니에 담은 모든 물건을 사기에는 돈이 부족하다는 것을 알았다. 고민하던 끝에 Ryu는 일부 물건들을 장바구니에서 뺐다. Ryu가 사온 물건들을 본 Han은 재료를 다 사지 않았어도 요리를 만드는 데 충분하다고 하였다.

오늘 철수의 결혼식에 많은 사람들이 모였다. 철수는 이렇게 모인 사람들 중 가장 어린 사람의 나이와 가장 나이가 많은 사람의 나이가 궁금해졌다. 사람들의 나이가 입력으로 주어졌을 때 최솟값과 최댓값을 구하여라.

제약사항
시간제한 : 1 초

입력
첫 줄에 사람의 수 N(1 ≤ N ≤ 1000) 이 주어지고 다음 줄에 N명의 나이가 자연수로 주어진다. 나이는 1이상 150 이하의 자연수이다.

출력
나이의 최솟값과 최댓값을 공백을 사이에 두고 출력한다.

우리나라의 8월에는 한 밤중에도 온도가 25도를 넘는 열대야 현상이 나타난다. 이 때, 많은 사람들이 잠을 설치고 고생한다. 특별히 며칠째 연속적으로 열대야가 계속되는 경우도 있다.

각 날의 한 밤중 온도가 순서대로 주어 질 때, 연속적으로 가장 길게 열대야 현상이 나타났을 때 그 길이를 출력하는 프로그램을 작성하시오.
예를 들어, 한 밤중의 온도들이 다음과 같이 주어진다면:
20 21 26 24 25 27 23 23 25 28 26 24 23 25
가장 길게 연속적으로 열대야 현상이 나타난 부분은 9번째 날(25℃)부터 11번째 날(26℃)의 3일이다

제약사항
시간제한 : 1 초

입력
입력의 첫째 줄에는 온도가 주어지는 전체 날들의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄에는 각 날의 온도를 순서대로 나타내는 N 개의 정수 a(1 ≤ a ≤ 40)가 빈 칸을 사이에 두고 주어진다.

출력
가장 길게 연속적으로 열대야 현상이 나타난 경우의 그 길이를 출력한다.

369는 사람들이 모였을 때 자주 하는 게임이다. 이 게임에서는 사람들이 둥글게 둘러 앉아서, 차례대로 사람들이 1부터 시작하여 하나씩 증가하는 숫자를 불러 나간다. 만약 자기 차례에서 불러야 할 숫자가 다음 조건 중 하나를 만족하면 숫자를 부르는 대신 박수를 친다.

- 이 숫자가 3의 배수일 때
- 숫자에 3, 6, 9가 포함되어 있을 때

예를 들자면, 1부터 시작하여 숫자를 불러 나가고, 박수를 X로 표현한다면, 다음과 같이 진행된다. 13에는 3이 포함되기 때문에 박수를 쳐야 한다는데 주의하시오.

1 – 2 – X – 4 – 5 – X – 7 – 8 – X – 10 – 11- X – X – 14 – X - ...

만약 이 게임을 1부터 시작하지 않고, 1보다 같거나 큰 숫자 a부터 시작하여 b에서 끝날 때까지 진행한다면, 박수를 총 몇 번 치게 되는지 계산하는 프로그램을 작성하라.

제약사항
시간제한 : 1 초

입력
입력은 한 줄로 이루어져 있고, 두 자연수 a와 b가 주어진다 (1 ≤ a ≤ b ≤ 5,000).

출력
박수를 치는 횟수를 하나의 자연수로 출력한다.

N x N 격자 미로가 있다. 각 칸에는 0 이상의 정수가 저장되어 있다. 미로의 가장 왼쪽 위 칸이 (1, 1)이고, 가장 오른쪽 아래 칸이 (N, N) 이다. 개구리 한 마리가 미로의 (1, 1) 칸에 갇혀 있다. 미로의 탈출 통로는 칸과 유일하게 연결되어 있어 반드시 칸에 도달해야 탈출 가능하다. 개구리는 자신이 위치한 현재 칸에 저장된 숫자만큼 자신의 오른쪽 방향이나 아래쪽 방향으로 칸들을 점프해서 이동할 수 있다. 만약 개구리가 현재 칸에 있고 2가 해당 칸의 숫자라면, 개구리는 또는 칸으로 점프해서 이동할 수 있다. 저장된 값이 0인 칸은 우물을 의미하고, 점프해서 이 칸으로 이동하면 개구리는 우물에 빠져 영원히 탈출할 수 없다. 만약 격자 미로 밖으로 점프하게 되면, 개구리는 목숨을 잃게 되어 역시 탈출할 기회가 사라진다.

N x N 격자판 미로와 각 칸의 0 이상의 정수가 주어진 경우, (1, 1) 칸에 있는 개구리가 (N, N) 칸에 도달할 수 있는지 없는지 결정하는 프로그램을 작성하라.

제약사항
시간제한 : 1 초

입력
입력의 첫 줄에는 N이 주어진다 (2 ≤ N ≤ 1,000). 다음 N개의 줄에는 N x N 격자 미로의 칸에 저장된 0 이상의 정수가 주어진다. 첫 줄에는 격자 미로의 첫 번째 행에 있는 칸들의 정수 개가 차례로 주어진다. 즉, (1, 1),(1, 2), ...(1, N) 칸의 정수가 차례로 주어진다. 두 번째 줄에는 두 번째 행에 있는 칸들의 정수 N개가 주어진다. 이런 방식으로 N번째 줄에는 마지막 행의 칸들의 정수가 주어진다. 칸들의 정수는 0이상 N이하의 정수이다. (N ≤ 1,000 범위는 테스트 데이터를 만든 후 조정해도 됨!)

출력
(1, 1) 칸에 있는 개구리가 (N, N)칸에 도달할 수 있다면 1을 출력하고 도달할 수 없다면 0을 출력한다.

매우 중요한 자료구조로 사용되는 AVL 트리는 각 노드의 두 자식 부트리(child subtree)의 높이 차가 1 이하인 이진트리로 정의된다. 이진트리의 높이는 루트노드에서 가장 먼 리프노드까지의 경로의 길이이다. 경로의 길이는 경로를 구성하는 에지의 개수이다. 노드 하나만으로 구성된 이진트리의 높이는 0으로 정의되며, 당연히 AVL 트리이다.

가장 적은 개수의 노드로 구성된 높이가 h인 AVL트리를 T(h)라고 한다. A(h)는 T(h)의 노드 개수이다.
예를 들어, A(0)=1, A(2)=4이다. 트리 높이 h ≥ 0 가 주어지면, A(h)를 계산하는 프로그램을 작성하라.

제약사항
시간제한 : 1 초

입력
입력으로는 AVL트리의 높이 h가 주어진다 (0 ≤ h ≤ 40).

출력
A(h) 값을 출력한다.