摆书

题号：NC251466
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小明最近在家忙于整理书架，小明有 $n$ 本书，排成一行，每本书都有一个编号 $a_i$ 。

小明每次操作可以交换相邻的两本书。小明有一些特别讨厌的书，

他希望用最少的操作次数使得区间 $[l,r]$ 不含有编号为 $x$ 的书本，每次操作独立。

输入共 $m+2$ 行。

第一行一个整数表示 $n,m\ (1≤n,m≤ 10^5)$ 。

接下来一行，每行一个整数表示 $a_i\ (1≤a_i≤n)$ 。

接下来 $m$ 行，每行 $3$ 个正整数， $l,r,x\ (1≤l,r,x≤n,l≤r)$ 表示使得区间 $[l,r]$ 不含有 $x$ 。

输出共  行，表示最小操作次数，无解输出 -1 。

示例1

复制

9 3
1 3 2 3 3 1 3 2 2
2 4 3
5 5 1
1 6 3

复制

3
0
-1

第一问，区间为[2,4]时，先交换(1,2)，再交换(5,6)，最后交换(4,5)，操作数为3。
第二问，区间本来就不含1，输出0。
第三问，无论怎么交换，区间[1,6]都有3，输出-1。