Alice has recently received an array a_1, a_2, ..., a_n for her birthday! She is very proud of her array, and when she showed her friend Bob the array, he was very happy with her present too!

However, soon Bob became curious, and as any sane friend would do, asked Alice to perform q operations of two types on her array:

  * 1 x y: update the element a_x to y (set a_x = y). 
  * 2 l r: calculate how many non-decreasing subarrays exist within the subarray [a_l, a_{l+1}, ..., a_r]. More formally, count the number of pairs of integers (p,q) such that l ≤ p ≤ q ≤ r and a_p ≤ a_{p+1} ≤ ... ≤ a_{q-1} ≤ a_q. 



Help Alice answer Bob's queries!

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 2 ⋅ 10^5) — the size of the array, and the number of queries, respectively.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the elements of Alice's array.

The next q lines consist of three integers each. The first integer of the i-th line is t_i, the operation being performed on the i-th step (t_i = 1 or t_i = 2).

If t_i = 1, the next two integers are x_i and y_i (1 ≤ x_i ≤ n; 1 ≤ y_i ≤ 10^9), updating the element at position x_i to y_i (setting a_{x_i} = y_i).

If t_i = 2, the next two integers are l_i and r_i (1 ≤ l_i ≤ r_i ≤ n), the two indices Bob asks Alice about for the i-th query.

It's guaranteed that there is at least one operation of the second type.

Output

For each query of type 2, print a single integer, the answer to the query.

Example

Input


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


Output


6
4
10
7

Note

For the first query, l = 2 and r = 5, and the non-decreasing subarrays [p,q] are [2,2], [3,3], [4,4], [5,5], [2,3] and [4,5].
import java.util.*;

public class E {

	public Object solve () {
		int N = sc.nextInt(), Q = sc.nextInt();
		int [] A = sc.nextInts();

		TreeSet<Integer> K = new TreeSet<>();
		Fenwick F = new Fenwick(N);

		for (int p = 0; p < N; ) {
			K.add(p);
			int q; for (q = p+1; q < N && A[q] >= A[q-1]; ++q);
			F.add(calc(p, q), p);
			p = q;
		}
		K.add(N);

		for (@SuppressWarnings("unused") int q : rep(Q))
			switch(sc.nextInt()) {
			case 1:
				int x = sc.nextInt() - 1, y = sc.nextInt();
				int a = K.floor(x), b = K.higher(a);

				if (a < x && y < A[x-1]) {
					K.add(x);
					F.add(calc(a, x) - calc(a, b), a);
					F.add(calc(x, b), x);
					a = x;
				}

				if (b > x+1 && y > A[x+1]) {
					K.add(x+1);
					F.add(calc(a, x+1) - calc(a, b), a);
					F.add(calc(x+1, b), x+1);
					b = x+1;
				}

				if (a == x && x > 0 && y >= A[x-1]) {
					K.remove(x); a = K.lower(a);
					F.add(calc(a, b) - calc(a, x), a);
					F.add(-calc(x, b), x);
				}

				if (b == x+1 && x < N-1 && y <= A[x+1]) {
					K.remove(x+1); b = K.higher(b);
					F.add(calc(a, b) - calc(a, x+1), a);
					F.add(-calc(x+1, b), x+1);
				}

				A[x] = y;
				break;

			case 2:
				int L = sc.nextInt() - 1, R = sc.nextInt();
				a = K.higher(L); b = K.lower(R);

				if (R <= a) {
					print(calc(L, R));
					break;
				}

				long res = calc(L, a) + F.get(a, b) + calc(b, R);
				print(res);
				break;
			}

		return null;
	}

	long calc (int p, int q) {
		long L = q - p;
		long res = L * (L + 1) / 2;
		return res;
	}

	private static final int CONTEST_TYPE = 1;

	private static void init () {
	}

	/**
	 * For every i in [0,N), bits[i] is the list of i's bits, in increasing order.
	 */
	int [][] bits (int N) {
		int M = 1 << N;
		int [][] res = new int [M][];
		for (int m = 0; m < M; ++m) {
			res[m] = new int [Integer.bitCount(m)];
			int t = m;
			for (int i = 0; i < res[m].length; ++i) {
				int j = (t & (-t));
				res[m][i] = Integer.numberOfTrailingZeros(j);
				t -= j;
			}
		}
		return res;
	}
	private static int [] rep (int N) { return rep(0, N); }
	private static int [] rep (int S, int T) { if (S >= T) return new int [0]; int [] res = new int [T-S]; for (int i = S; i < T; ++i) res[i-S] = i; return res; }
	private static class Fenwick {
		private final long [] X;
		private final long mod;
		public Fenwick (int N) { this(N, 0); }
		public Fenwick (int N, int mod) { X = new long [N]; this.mod = mod; }
		public void add (long x, int i) {
			++i; assert i <= X.length;
			while (i <= X.length) {
				X[i-1] += x;
				if (mod > 0) X[i-1] = ((X[i-1] % mod) + mod) % mod;
				i += (i & (-i));
			}
		}
		public long get (int to) {
			assert to <= X.length;
			long res = 0;
			for (; to > 0; to -= (to & (-to))) {
				res += X[to-1];
				if (mod > 0) res = ((res % mod) + mod) % mod;
			}
			return res;
		}
		public long get (int from, int to) {
			assert from <= to;
			long res = get(to) - get(from);
			if (mod > 0) res = ((res % mod) + mod) % mod;
			return res;
		}
	}
	//////////////////////////////////////////////////////////////////////////////////// OFF
	private static IOUtils.MyScanner sc = new IOUtils.MyScanner();
	private static Object print (Object o, Object ... A) { IOUtils.print(o, A); return null; }
	private static class IOUtils {
		public static class MyScanner {
			public String next () { newLine(); return line[index++]; }
			public int nextInt () { return Integer.parseInt(next()); }
			public String nextLine () { line = null; return readLine(); }
			public String [] nextStrings () { return split(nextLine()); }
			public int [] nextInts () {
				String [] S = nextStrings(); int N = S.length;
				int [] res = new int [N];
				for (int i = 0; i < N; ++i)
					res[i] = Integer.parseInt(S[i]);
				return res;
			}
			//////////////////////////////////////////////
			private boolean eol () { return index == line.length; }
			private String readLine () {
				try {
					int b;
					StringBuilder res = new StringBuilder();
					while ((b = System.in.read()) < ' ')
						continue;
					res.append((char)b);
					while ((b = System.in.read()) >= ' ')
						res.append((char)b);
					return res.toString();
				} catch (Exception e) {
					throw new Error (e);
				}
			}
			private MyScanner () {
				try {
					while (System.in.available() == 0)
						Thread.sleep(1);
					start();
				} catch (Exception e) {
					throw new Error(e);
				}
			}
			private String [] line;
			private int index;
			private void newLine () {
				if (line == null || eol()) {
					line = split(readLine());
					index = 0;
				}
			}
			private String [] split (String s) { return s.length() > 0 ? s.split(" ") : new String [0]; }
		}
		private static String build (Object o, Object ... A) { return buildDelim(" ", o, A); }
		private static String buildDelim (String delim, Object o, Object ... A) {
			java.util.List<String> str = new java.util.ArrayList<>();
			append(str, o);
			for (Object p : A)
				append(str, p);
			return String.join(delim, str.toArray(new String [0]));
		}
		//////////////////////////////////////////////////////////////////////////////////
		private static java.text.DecimalFormat formatter = new java.text.DecimalFormat("#.#########");
		private static void start () { if (t == 0) t = millis(); }
		private static void append (java.util.function.Consumer<Object> f, java.util.function.Consumer<Object> g, Object o) {
			if (o.getClass().isArray()) {
				int len = java.lang.reflect.Array.getLength(o);
				for (int i = 0; i < len; ++i)
					f.accept(java.lang.reflect.Array.get(o, i));
			}
			else if (o instanceof Iterable<?>)
				((Iterable<?>)o).forEach(f::accept);
			else
				g.accept(o instanceof Double ? formatter.format(o) : o);
		}
		private static void append (java.util.List<String> str, Object o) {
			append(x -> append(str, x), x -> str.add(x.toString()), o);
		}
		private static java.io.PrintWriter pw = new java.io.PrintWriter(System.out);
		private static void flush () { pw.flush(); System.out.flush(); }
		private static void print (Object o, Object ... A) {
			String res = build(o, A);
			if (DEBUG == 2)
				err(res, '(', time(), ')');
			if (res.length() > 0)
				pw.println(res);
			if (DEBUG == 1)
				flush();
		}
		private static void err (Object o, Object ... A) { System.err.println(build(o, A)); }
		private static int DEBUG;
		private static void exit () {
			String end = "------------------" + System.lineSeparator() + time();
			switch(DEBUG) {
			case 1: print(end); break;
			case 2: err(end); break;
			}
			IOUtils.pw.close();
			System.out.flush();
			System.exit(0);
		}
		private static long t;
		private static long millis () { return System.currentTimeMillis(); }
		private static String time () { return "Time: " + (millis() - t) / 1000.0; }
		private static void run (int N) {
			try { DEBUG = Integer.parseInt(System.getProperties().get("DEBUG").toString()); }
			catch (Throwable t) {}

			for (int n = 1; n <= N; ++n) {
				Object res = new E().solve();
				if (res != null) {
					@SuppressWarnings("all")
					Object o = CONTEST_TYPE == 0 ? "Case #" + n + ": " + build(res) : res;
					print(o);
				}
			}
			exit();
		}
	}
	////////////////////////////////////////////////////////////////////////////////////
	public static void main (String[] args) {
		@SuppressWarnings("all")
		int N = CONTEST_TYPE == 1 ? 1 : sc.nextInt();
		init();
		IOUtils.run(N);
	}
}
