이등변삼각형 벽

세르지우와 루이스 형제가 나무 큐브로 벽을 쌓았다. 벽은 끝까지 채우지 못해서 기둥마다 높이가 제각각이다.

두 사람은 이제 큐브를 빼내는 놀이를 하기로 했다. 큐브는 각 기둥의 맨 위에서부터만 빼낼 수 있고, 빼낸 큐브를 다른 기둥에 다시 올릴 수는 없다. 마지막에는 완전한 이등변삼각형 하나만 남아야 한다.

높이가 $h$인 이등변삼각형은 연속한 기둥 $2h-1$개로 이루어지고, 왼쪽부터 각 기둥의 높이가 정확히 $1, 2, \dots, h-1, h, h-1, \dots, 2, 1$이다. 아래 그림은 높이가 1, 2, 3, 4, 5인 이등변삼각형을 차례로 그린 것이다.

삼각형에 쓰이지 않는 기둥은 큐브를 하나도 남기지 않고 모두 빼내야 한다. 벽을 이루는 기둥의 높이가 순서대로 주어질 때, 마지막에 남길 수 있는 삼각형의 최대 높이를 구하는 프로그램을 작성하시오. 기둥이 30개인 첫 번째 그림의 벽에서는 높이가 7인 삼각형까지 남길 수 있다.

첫째 줄에 벽을 이루는 기둥의 개수 $N$이 주어진다. 둘째 줄에 각 기둥의 높이 $A_i$가 왼쪽부터 순서대로 $N$개 주어진다.

제한

• $1 \le N \le 50\,000$
• $1 \le A_i \le N$

마지막에 남길 수 있는 삼각형의 최대 높이 $H$를 한 줄에 출력한다.