CF #261 Div2 D. パシュマクとパルミダの問題 (離散化 + 逆順序ペア + セグメント ツリー)_html/css_WEB-ITnose

パルミダは賢い女の子で、今年はオリンピックに参加したいと思っています。もちろん、彼女はパートナーにも賢くなることを望んでいます（彼はそうではありませんが）！ Parmida では、Pashmak 用に次のテスト問題を用意しています。

n 個の整数 a1,?a2,?...,?an からなる数列 a があります。 l?≤?k?≤?rかつak?=?xとなるようなインデックスkの数をf(l,?r,?x)と表すことにする。彼のタスクは、 f(1,?i,?ai)?>?f(j となるようなインデックス i,?j (1?≤?i?

Pashmak のテストを手伝ってください。

入力

入力の最初の行には、整数 n (1?≤?n?≤?106) が含まれています。 2 行目には、スペースで区切られた n 個の整数 a1,?a2,?...,?an (1?≤?ai?≤?109) が含まれています。

出力

単一の整数を出力します。問題の答え。

サンプルテスト

入力

71 2 1 1 2 2 1

出力

入力

31 1 1

出力

入力

51 2 3 4 5

出力

目出た F 関数、可用性散布的方法加预处理 将每个F（1，i，x）と F（j，n，x）を求め、それぞれ f1 に保存、f2数組、那么题目就可转化可能： f1[i] > f2[j] && i

??