reference: https://www.acwing.com/solution/content/887/
const pr = console.log;
const solve = (n, a) => {
let max = Array(n + 1).fill(0), min = Array(n + 1).fill(0), cnt = 0, res = 0, monotonicity = true, h = 1 << 30;
a = a.map((x, i) => [x, i + 1]);
a.sort((x, y) => {
if (x[0] == y[0]) return x[1] - y[1];
return y[0] - x[0];
})
a.unshift([0, 0]);
for (let i = 1; i <= n; i++) {
if (a[i][0] != a[i - 1][0] || i == 1) {
max[cnt] = a[i - 1][1];
min[++cnt] = a[i][1];
}
}
max[cnt] = a[n][1];
for (let i = 1; i <= cnt; i++) {
if (!monotonicity) {
if (h > max[i]) {
h = min[i];
} else {
h = max[i];
monotonicity = true;
}
} else {
if (h < min[i]) {
h = max[i];
} else {
h = min[i];
monotonicity = false;
res++;
}
}
}
pr(res);
};
const main = () => {
const readLine = () => input[currentLine++];
const ni = () => readLine() - '0';
const nas = () => readLine().split(" ");
const nai = () => nas().map(Number);
const nal = () => nas().map(BigInt);
let input = '', currentLine = 0;
process.stdin.on('data', (stdin) => input += stdin)
process.stdin.on('end', () => {
input = input.split('\n');
let n = ni(), a = [];
for (let i = 0; i < n; i++) a.push(ni())
solve(n, a);
});
};
main()