Vasya adores sport programming. He can't write programs but he loves to watch the contests' progress. Vasya even has a favorite coder and Vasya pays special attention to him.

One day Vasya decided to collect the results of all contests where his favorite coder participated and track the progress of his coolness. For each contest where this coder participated, he wrote out a single non-negative number — the number of points his favorite coder earned in the contest. Vasya wrote out the points for the contest in the order, in which the contests run (naturally, no two contests ran simultaneously).

Vasya considers a coder's performance in a contest amazing in two situations: he can break either his best or his worst performance record. First, it is amazing if during the contest the coder earns strictly more points that he earned on each past contest. Second, it is amazing if during the contest the coder earns strictly less points that he earned on each past contest. A coder's first contest isn't considered amazing. Now he wants to count the number of amazing performances the coder had throughout his whole history of participating in contests. But the list of earned points turned out long and Vasya can't code... That's why he asks you to help him.

Input

The first line contains the single integer n (1 ≤ n ≤ 1000) — the number of contests where the coder participated.

The next line contains n space-separated non-negative integer numbers — they are the points which the coder has earned. The points are given in the chronological order. All points do not exceed 10000.

Output

Print the single number — the number of amazing performances the coder has had during his whole history of participating in the contests.

Examples

Input

5
100 50 200 150 200


Output

2


Input

10
4664 6496 5814 7010 5762 5736 6944 4850 3698 7242


Output

4

Note

In the first sample the performances number 2 and 3 are amazing.

In the second sample the performances number 2, 4, 9 and 10 are amazing.
5
100 36 53 7 81
 5
100 81 53 36 7
 10
8 6 3 4 9 10 7 7 1 3
 33
1097 1132 1091 1104 1049 1038 1023 1080 1104 1029 1035 1061 1049 1060 1088 1106 1105 1087 1063 1076 1054 1103 1047 1041 1028 1120 1126 1063 1117 1110 1044 1093 1101
 34
821 5536 2491 6074 7216 9885 764 1603 778 8736 8987 771 617 1587 8943 7922 439 7367 4115 8886 7878 6899 8811 5752 3184 3401 9760 9400 8995 4681 1323 6637 6554 6498
 10
1952 1862 1812 1746 1675 1627 1488 1390 1324 1137
 2
10 10
 2
5 5
 1
6
 1
0
 2
1 1
 2
0 10000
 2
2 1
 100
158 159 157 156 155 154 160 153 161 152 162 163 151 164 150 165 149 148 147 166 146 167 145 144 143 142 168 141 169 170 140 139 138 137 171 136 135 134 172 173 174 133 175 132 177 178 131 179 180 130 129 181 128 127 182 126 183 125 124 184 123 122 121 120 119 118 117 185 186 187 188 189 116 190 115 191 192 193 114 113 112 111 110 109 108 194 195 107 106 105 196 197 104 198 199 103 102 200 101 100
 10
1627 1675 1488 1390 1812 1137 1746 1324 1952 1862
 25
1448 4549 2310 2725 2091 3509 1565 2475 2232 3989 4231 779 2967 2702 608 3739 721 1552 2767 530 3114 665 1940 48 4198
 10
1 3 3 4 6 7 7 8 9 10
 100
9999 9999 9999 9998 9998 9998 9997 9996 9996 9995 9993 9993 9991 9990 9989 9986 9984 9984 9983 9981 9981 9980 9980 9980 9979 9977 9977 9977 9977 9977 9976 9976 9975 9975 9973 9972 9972 9972 9972 9971 9969 9969 9969 9968 9967 9965 9962 9962 9962 9962 9960 9958 9958 9955 9954 9954 9954 9954 9950 9949 9949 9947 9943 9943 9940 9940 9939 9937 9937 9937 9936 9935 9932 9932 9931 9929 9927 9927 9926 9923 9919 9919 9918 9918 9918 9917 9917 9916 9916 9915 9914 9911 9910 9907 9907 9906 9905 9905 9904 9901
 5
7 36 53 81 100
 100
7 61 12 52 41 16 34 99 30 44 48 89 31 54 21 1 48 52 61 15 35 87 21 76 64 92 44 81 16 93 84 92 32 15 68 76 53 39 26 4 11 26 7 4 99 99 61 65 55 85 65 67 47 39 2 74 63 49 98 87 5 94 22 30 25 42 31 84 49 23 89 60 16 26 92 27 9 57 75 61 94 35 83 47 99 100 63 24 91 88 79 10 15 45 22 64 3 11 89 83
 68
6764 6877 6950 6768 6839 6755 6726 6778 6699 6805 6777 6985 6821 6801 6791 6805 6940 6761 6677 6999 6911 6699 6959 6933 6903 6843 6972 6717 6997 6756 6789 6668 6735 6852 6735 6880 6723 6834 6810 6694 6780 6679 6698 6857 6826 6896 6979 6968 6957 6988 6960 6700 6919 6892 6984 6685 6813 6678 6715 6857 6976 6902 6780 6686 6777 6686 6842 6679
 60
9000 9014 9034 9081 9131 9162 9174 9199 9202 9220 9221 9223 9229 9235 9251 9260 9268 9269 9270 9298 9307 9309 9313 9323 9386 9399 9407 9495 9497 9529 9531 9544 9614 9615 9627 9627 9643 9654 9656 9657 9685 9699 9701 9736 9745 9758 9799 9827 9843 9845 9854 9854 9885 9891 9896 9913 9942 9963 9986 9992

2
 4
 5
 5
 7
 9
 0
 0
 0
 0
 0
 1
 1
 99
 6
 5
 7
 57
 4
 4
 9
 57

//package CodeforcesLadder;

import java.util.HashSet;
import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] arr = new int[n];
        int smallest = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
            if (arr[i] < smallest) {
                smallest = arr[i];
            }
        }
        if(n == 1) {
            System.out.println(0);
            return;
        }
        int c = 0;
        int temp = arr[0];
        if(temp == smallest) {
            c++;
        }
        System.out.println(smallest);
        System.out.println(temp);
        for (int i = 1; i < n; i++) {
            if(arr[i] > temp) {
                temp = arr[i];
                c++;
            }
            else if(arr[i] == smallest) {
                c++;
            }
        }
        System.out.println(c);
    }
}
