여기서 우리는 진수가 게임을 시작할 수 있도록 완벽한 닉네임을 찾아주었다. 어느덧 고인물이 된 진수는, 최종 보스 공략을 목전에 두고 있다.

최종 보스를 공략하기 위해서는 다음의 규칙을 따라야 한다.

• $N$개의 페이즈는 반드시 순서대로 공략되어야 한다.
• $i$번째 페이즈를 공략하기 위해서는 최소 $p_i$의 공격력을 가진 무기가 필요하다.
• $i$번째 페이즈를 공략했다면, 지금 들고 있는 무기의 공격력이 $p_i$가 된다.
• 지금 들고 있는 무기로 현재 페이즈 공략이 불가능하다면, 이를 버리고 가방에서 새로운 무기를 꺼내어 임의의 공격력을 부여할 수 있다.
• 첫 번째 페이즈에서는 당연히 새 무기를 꺼내들어 임의의 공격력을 부여한다.

진수는 수많은 시행착오를 거쳐 수열 $p_1, p_2, ... p_N$을 모두 계산해내었다.

그러나 이 과정에서 갖고 있는 무기를 모두 사용해버린 진수는, 우리에게 수열 $p_1, p_2, ... , p_N$을 주며 던전을 클리어하기 위해 필요한 최소한의 무기를 보내 달라고 했다. 진수에게 보낼 최소한의 무기 개수를 계산해보자!

첫째 줄에 페이즈의 수를 의미하는 정수 $N$이 주어진다.$(1 ≤ N ≤ 200,000)$

둘째 줄에 $p_1, p_2, ... , p_N$이 공백으로 구분되어 주어진다. $(1 ≤ p_i ≤ 10^9)$