def solve(io) n, q = io.get2 a = io.get_a(n) a2 = a.map_with_index { |ai, i| {ai, i} } a2.sort_by! { |ai, _| -ai } c = Array.new(n, -1) c2 = [] of Int32 a2.each do |_, i| c[i] = c2.bsearch { |j| j < i } || -1 c2.push(i) c2.sort! { |a, b| b <=> a } end b = Array.new(n, -1) aat = AATree(Int32).new a2.each do |_, i| b[i] = aat.rsearch { |j| j < i } || -1 aat.insert(i) end b2 = b.map_with_index { |bi, i| {bi, i} } b2.sort_by! { |bi, _| bi } r = Array.new(q) do |i| ti, li, ri = io.get3; li -= 1; ri -= 1 {li, ri, i} end r.sort_by! { |li, _, _| li } j = 0 ft = FenwickTree(Int32).new(n) ans = Array.new(q, 0) r.each do |li, ri, i| while b2[j][0] < li ft.add(b2[j][1], 1) j += 1 end ans[i] = ft[li..ri] end ans.each do |v| io.put v end end class ProconIO def initialize(@ins : IO = STDIN, @outs : IO = STDOUT) @buf = IO::Memory.new("") end def get(k : T.class = Int32) forall T get_v(k) end macro define_get {% for i in (2..9) %} def get({{ *(1..i).map { |j| "k#{j}".id } }}) { {{ *(1..i).map { |j| "get(k#{j})".id } }} } end {% end %} end define_get macro define_getn {% for i in (2..9) %} def get{{i}}(k : T.class = Int32) forall T get({{ *(1..i).map { "k".id } }}) end {% end %} end define_getn def get_a(n : Int, k : T.class = Int32) forall T Array.new(n) { get_v(k) } end def get_c(n : Int, k : T.class = Int32) forall T get_a(n, k) end macro define_get_c {% for i in (2..9) %} def get_c(n : Int, {{ *(1..i).map { |j| "k#{j}".id } }}) a = Array.new(n) { get({{ *(1..i).map { |j| "k#{j}".id } }}) } { {{ *(1..i).map { |j| "a.map { |e| e[#{j-1}] }".id } }} } end {% end %} end define_get_c macro define_getn_c {% for i in (2..9) %} def get{{i}}_c(n : Int, k : T.class = Int32) forall T get_c(n, {{ *(1..i).map { "k".id } }}) end {% end %} end define_getn_c def get_m(r : Int, c : Int, k : T.class = Int32) forall T Array.new(r) { get_a(c, k) } end macro define_put {% for i in (1..9) %} def put({{ *(1..i).map { |j| "v#{j}".id } }}, *, delimiter = " ") {% for j in (1..i) %} print_v(v{{j}}, delimiter) {% if j < i %}@outs << delimiter{% end %} {% end %} @outs.puts end {% end %} end define_put def put_e(*vs) put(*vs) exit end def put_f(*vs) put(*vs) @outs.flush end private def get_v(k : Int32.class); get_token.to_i32; end private def get_v(k : Int64.class); get_token.to_i64; end private def get_v(k : UInt32.class); get_token.to_u32; end private def get_v(k : UInt64.class); get_token.to_u64; end private def get_v(k : Float64.class); get_token.to_f64; end private def get_v(k : String.class); get_token; end private def get_token loop do token = @buf.gets(' ', chomp: true) break token unless token.nil? @buf = IO::Memory.new(@ins.read_line) end end private def print_v(v, dlimiter) @outs << v end private def print_v(v : Enumerable, delimiter) v.each_with_index do |e, i| @outs << e @outs << delimiter if i < v.size - 1 end end end struct Int def cdiv(b : Int) (self + b - 1) // b end def bit?(i : Int) bit(i) == 1 end def set_bit(i : Int) self | (self.class.new(1) << i) end def reset_bit(i : Int) self & ~(self.class.new(1) << i) end {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "0.35.0") < 0 %} def digits(base = 10) raise ArgumentError.new("Invalid base #{base}") if base < 2 raise ArgumentError.new("Can't request digits of negative number") if self < 0 return [0] if self == 0 num = self digits_count = (Math.log(self.to_f + 1) / Math.log(base)).ceil.to_i ary = Array(Int32).new(digits_count) while num != 0 ary << num.remainder(base).to_i num = num.tdiv(base) end ary end {% end %} {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "0.34.0") < 0 %} def bit_length : Int32 x = self < 0 ? ~self : self if x.is_a?(Int::Primitive) Int32.new(sizeof(self) * 8 - x.leading_zeros_count) else to_s(2).size end end {% end %} end struct Float64 def near?(x) (self - x).abs <= (self.abs < x.abs ? x.abs : self.abs) * EPSILON end end struct Number {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "1.1.0") < 0 %} def zero? self == 0 end def positive? self > 0 end def negative? self < 0 end {% end %} {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "0.36.0") < 0 %} def self.additive_identity zero end def self.multiplicative_identity new(1) end {% end %} end class Array macro new_md(*args, &block) {% if !block %} {% for arg, i in args[0...-2] %} Array.new({{arg}}) { {% end %} Array.new({{args[-2]}}, {{args[-1]}}) {% for arg in args[0...-2] %} } {% end %} {% else %} {% for arg, i in args %} Array.new({{arg}}) { |_i{{i}}| {% end %} {% for block_arg, i in block.args %} {{block_arg}} = _i{{i}} {% end %} {{block.body}} {% for arg in args %} } {% end %} {% end %} end end module Math {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "1.2.0") < 0 %} def isqrt(value : Int::Primitive) raise ArgumentError.new "Input must be non-negative integer" if value < 0 return value if value < 2 res = value.class.zero bit = res.succ << (res.leading_zeros_count - 2) bit >>= value.leading_zeros_count & ~0x3 while (bit != 0) if value >= res + bit value -= res + bit res = (res >> 1) + bit else res >>= 1 end bit >>= 2 end res end {% end %} end macro min_u(a, b) {{a}} = Math.min({{a}}, {{b}}) end macro max_u(a, b) {{a}} = Math.max({{a}}, {{b}}) end macro zip(a, *b, &block) {{a}}.zip({{*b}}) {{block}} end class FenwickTree(T) def initialize(@n : Int32) @b = Array.new(@n + 1, T.additive_identity) end def [](i : Int) self[i..i] end def [](start : Int, count : Int) get(start + count) - get(start) end def [](r : Range) sc = Indexable.range_to_index_and_count(r, @n) raise ArgumentError.new("Invalid range") if sc.nil? self[*sc] end def add(i : Int, val : T) i += 1 while i <= @n @b[i] += val i += i & -i end end @b : Array(T) private def get(i : Int) s = T.additive_identity while i > 0 s += @b[i] i -= i & -i end s end end class AATree(T) def initialize @root = NilNode(T).instance @cmp = ->(a : T, b : T) { a <=> b } end @root : Node(T) @cmp : (T, T) -> Int32 def debug @root.debug(@root.height) end def search(&block : T -> Bool) node = search_node(@root, block) node.nil_node? ? nil : node.key end def rsearch(&block : T -> Bool) node = rsearch_node(@root, block) node.nil_node? ? nil : node.key end def insert(key : T) @root = insert(@root, key) end def delete(key : T) @root = delete(@root, key) end def min_node(node : Node(T)) until node.left.nil_node? node = node.left end node end def max_node(node : Node(T)) until node.right.nil_node? node = node.right end node end def search_node(node : Node(T), block : T -> Bool) last : Node(T) = NilNode(T).instance loop do if block.call(node.key) last = node if node.left.nil_node? break last else node = node.left end else if node.right.nil_node? break last else node = node.right end end end end def rsearch_node(node : Node(T), block : T -> Bool) last : Node(T) = NilNode(T).instance loop do if block.call(node.key) last = node if node.right.nil_node? break last else node = node.right end else if node.left.nil_node? break last else node = node.left end end end end def insert(node : Node(T), key : T) if node.nil_node? return Node.new(key) elsif @cmp.call(key, node.key).negative? node.left = insert(node.left, key) else node.right = insert(node.right, key) end split(skew(node)) end def delete(node : Node(T), key : T) unless node.nil_node? if @cmp.call(key, node.key).zero? if node.left.nil_node? return node.right elsif node.right.nil_node? return node.left else node.key = min_node(node.right).key node.right = delete(node.right, node.key) end elsif @cmp.call(key, node.key).negative? node.left = delete(node.left, key) else node.right = delete(node.right, key) end if node.left.height < node.height - 1 || node.right.height < node.height - 1 node.height -= 1 if node.right.height > node.height node.right.height = node.height end node = skew(node) node.right = skew(node.right) node.right.right = skew(node.right.right) node = split(node) node.right = split(node.right) end end node end def skew(node : Node(T)) if node.left.height == node.height node = rotate_right(node) end node end def split(node : Node(T)) if node.height == node.right.right.height node = rotate_left(node) node.height += 1 end node end def rotate_right(node : Node(T)) lnode = node.left node.left = lnode.right lnode.right = node lnode end def rotate_left(node : Node(T)) rnode = node.right node.right = rnode.left rnode.left = node rnode end class Node(T) def initialize(@key : T) @height = 1 @left = NilNode(T).instance @right = NilNode(T).instance end property key : T property height : Int32 property left : Node(T) property right : Node(T) def debug(max_height) unless nil_node? left.debug(max_height) puts " " * (max_height - height) + key.to_s right.debug(max_height) end end def nil_node? false end end class NilNode(T) < Node(T) def self.instance node = new node.left = node node.right = node node end def initialize @key = uninitialized T @height = 0 @left = uninitialized Node(T) @right = uninitialized Node(T) end def debug end def nil_node? true end end end solve(ProconIO.new)