using System;
using System.Collections.Generic;
using System.Linq;
namespace Library
{
public class SegmentTree<T> where T: struct
{
private readonly T[] data;
private int size = 1;
private T defaultValue;
private Func<T, T, T> function;
public SegmentTree(int size, T defaultValue, Func<T, T, T> function)
{
while(this.size < size) this.size *= 2;
this.defaultValue = defaultValue;
this.function = function;
data = Enumerable.Repeat(defaultValue, this.size * 2 - 1).ToArray();
}
// [a, b)
public T RangedValue(int a, int b) { return RangedValue(a, b, 0, 0, size); }
private T RangedValue(int a, int b, int now, int l, int r)
{
if (r <= a || b <= l) return defaultValue;
if (a <= l && r <= b) return data[now];
return function(RangedValue(a, b, now * 2 + 1, l, (l + r) / 2), RangedValue(a, b, now * 2 + 2, (l + r) / 2, r));
}
public T this[int index]
{
get
{
return data[size + index - 1];
}
set
{
index += size - 1;
data[index] = value;
while (index > 0)
{
index = (index - 1) / 2;
data[index] = function(data[index * 2 + 1], data[index * 2 + 2]);
}
}
}
}
}
class Input {
static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();
public static string Line => Console.ReadLine();
public static string[] StrArr => Line.Split(' ');
public static int NextInt => int.Parse(NextWord());
public static long NextLong => long.Parse(NextWord());
public static List<int> IntList => StrArr.Select(int.Parse).ToList();
public static List<long> LongList => StrArr.Select(long.Parse).ToList();
public static string NextWord() {
while (!enumerator.MoveNext()) {
enumerator = StrArr.AsEnumerable().GetEnumerator();
}
return enumerator.Current;
}
}