#P1763. 2024.03.28-企鹅music-第四题-塔子哥的有序二叉树

2024.03.28-企鹅music-第四题-塔子哥的有序二叉树

题目描述

塔子哥拿到了一个二叉树，每个节点的权值都不相同。塔子哥每次操作可以交换任意两个节点的权值，他希望用尽可能少的操作，使得二叉树的先序遍历序列为一个升序的数组，你能帮帮他吗？

输入描述

第一行，一个整数 nn 表示二叉树中节点数量

第二行，nn 个整数 aia_i 表示二叉树先序遍历情况下每个节点的权值

1≤n≤106,1≤ai≤1091\leq n\leq 10^6, 1\leq a_i\leq 10^9

输出描述

一个整数，表示使得二叉树的先序遍历序列是一个升序数组的最少操作次数

样例

输入

3
1 3 2

输出

1

知识点:*****

查看知识点以及同类型题目

Statistics