Day at the Beach

题意翻译

一天Squidward，Spongebob，Patrick决定一起去沙滩玩。不幸的是，天气实在不好，他们没法冲浪了。然鹅，他们决定建一个沙堡。 那天快结束的时候，他们建了n个城堡。城堡被编号为1到n，第i个城堡的高度是hi。就在大家都要走的时候，Squidward注意到，沙堡没有按它们的高度排序，这看起来很不和谐,。现在，他们将重新排列城堡，使对于所有的i，（0<=i<=n-1）都有hi<=hi+1。 Squidward建议用下列方式给城堡排序： - 城堡被分成几个连续的段，因此从i到j的城堡段应该包括i,i+1...j-1,j。一个城堡段可以只有一个城堡组成。 - 使所有城堡都在一个段内。 - 每个段独立于其他段进行排序，即序列hi,hi+1...hj-1,hj是有序的。 - 段的划分应满足在每个段被排序之后，序列也变得有序。这总是可以被满足因为可以把整个序列看做一段。 Patrick知道在分区中增加块的数量将简化排序过程。现在，他们要求你计算满足所有上述要求的分区中的最大可能块数。 输入输出格式 输入格式： 第一行包括一个数n(1<=n<=100000)，表示Spongebob, Patrick和Squidward建的城堡的数量。 下一行包括n个整数hi(1<=hi<=1e9)。第i个数表示第i个城堡的高度。 输出格式： 输出最大可能的序列被划分的段数。

题目描述

One day Squidward, Spongebob and Patrick decided to go to the beach. Unfortunately, the weather was bad, so the friends were unable to ride waves. However, they decided to spent their time building sand castles. At the end of the day there were $ n $ castles built by friends. Castles are numbered from $ 1 $ to $ n $ , and the height of the $ i $ -th castle is equal to $ h_{i} $ . When friends were about to leave, Squidward noticed, that castles are not ordered by their height, and this looks ugly. Now friends are going to reorder the castles in a way to obtain that condition $ h_{i}<=h_{i+1} $ holds for all $ i $ from $ 1 $ to $ n-1 $ . Squidward suggested the following process of sorting castles: - Castles are split into blocks — groups of consecutive castles. Therefore the block from $ i $ to $ j $ will include castles $ i,i+1,...,j $ . A block may consist of a single castle. - The partitioning is chosen in such a way that every castle is a part of exactly one block. - Each block is sorted independently from other blocks, that is the sequence $ h_{i},h_{i+1},...,h_{j} $ becomes sorted. - The partitioning should satisfy the condition that after each block is sorted, the sequence $ h_{i} $ becomes sorted too. This may always be achieved by saying that the whole sequence is a single block. Even Patrick understands that increasing the number of blocks in partitioning will ease the sorting process. Now friends ask you to count the maximum possible number of blocks in a partitioning that satisfies all the above requirements.

输入输出格式

输入格式

The first line of the input contains a single integer $ n $ ( $ 1<=n<=100000 $ ) — the number of castles Spongebob, Patrick and Squidward made from sand during the day. The next line contains $ n $ integers $ h_{i} $ ( $ 1<=h_{i}<=10^{9} $ ). The $ i $ -th of these integers corresponds to the height of the $ i $ -th castle.

输出格式

Print the maximum possible number of blocks in a valid partitioning.

输入输出样例

输入样例 #1

3
1 2 3

输出样例 #1

3

输入样例 #2

4
2 1 3 2

输出样例 #2

2

说明

In the first sample the partitioning looks like that: \[1\]\[2\]\[3\]. In the second sample the partitioning is: \[2, 1\]\[3, 2\]