Problem: You are given a permutation p_1, p_2, ..., p_n. You should answer q queries. Each query is a pair (l_i, r_i), and you should calculate f(l_i, r_i).

Let's denote m_{l, r} as the position of the maximum in subsegment p_l, p_{l+1}, ..., p_r.

Then f(l, r) = (r - l + 1) + f(l, m_{l,r} - 1) + f(m_{l,r} + 1, r) if l ≤ r or 0 otherwise.

Input

The first line contains two integers n and q (1 ≤ n ≤ 10^6, 1 ≤ q ≤ 10^6) — the size of the permutation p and the number of queries.

The second line contains n pairwise distinct integers p_1, p_2, ..., p_n (1 ≤ p_i ≤ n, p_i ≠ p_j for i ≠ j) — permutation p.

The third line contains q integers l_1, l_2, ..., l_q — the first parts of the queries.

The fourth line contains q integers r_1, r_2, ..., r_q — the second parts of the queries.

It's guaranteed that 1 ≤ l_i ≤ r_i ≤ n for all queries.

Output

Print q integers — the values f(l_i, r_i) for the corresponding queries.

Example

Input


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


Output


1 6 8 5 1 

Note

Description of the queries: 

  1. f(2, 2) = (2 - 2 + 1) + f(2, 1) + f(3, 2) = 1 + 0 + 0 = 1; 
  2. f(1, 3) = (3 - 1 + 1) + f(1, 2) + f(4, 3) = 3 + (2 - 1 + 1) + f(1, 0) + f(2, 2) = 3 + 2 + (2 - 2 + 1) = 6; 
  3. f(1, 4) = (4 - 1 + 1) + f(1, 2) + f(4, 4) = 4 + 3 + 1 = 8; 
  4. f(2, 4) = (4 - 2 + 1) + f(2, 2) + f(4, 4) = 3 + 1 + 1 = 5; 
  5. f(1, 1) = (1 - 1 + 1) + 0 + 0 = 1. 

Solution (in JAVA):

Solution:
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF1117G extends PrintWriter {
	CF1117G() { super(System.out, true); }
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		int k, l; byte[] bb = new byte[1 << 15];
		byte getc() {
			if (k >= l) {
				k = 0;
				try { l = in.read(bb); } catch (IOException e) { l = 0; }
				if (l <= 0) return -1;
			}
			return bb[k++];
		}
		int nextInt() {
			byte c = 0; while (c <= 32) c = getc();
			int a = 0;
			while (c > 32) { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
	}
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF1117G o = new CF1117G(); o.main(); o.flush();
	}

	long[] ss, cc;
	void update(long[] ft, int i, int n, int x) {
		while (i < n) {
			ft[i] += x;
			i |= i + 1;
		}
	}
	long query(long[] ft, int i) {
		long x = 0;
		while (i >= 0) {
			x += ft[i];
			i &= i + 1; i--;
		}
		return x;
	}
	int[] qu, pp;
	Integer[] ii, hh;
	void solve(int[] aa, int n, int[] ll, int[] rr, long[] ans, int q) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			while (cnt > 0 && aa[qu[cnt - 1]] <= aa[i])
				cnt--;
			pp[i] = cnt == 0 ? 0 : qu[cnt - 1] + 1;
			qu[cnt++] = i;
		}
		Arrays.fill(ss, 0);
		Arrays.fill(cc, 0);
		for (int i = 0; i < n; i++)
			update(ss, i, n, pp[i]);
		Arrays.sort(ii, (i, j) -> pp[i] - pp[j]);
		Arrays.sort(hh, (i, j) -> ll[i] - ll[j]);
		for (int h_ = 0, i_ = 0; h_ < q; h_++) {
			int h = hh[h_], i, l = ll[h], r = rr[h];
			while (i_ < n && pp[i = ii[i_]] < l) {
				update(ss, i, n, -pp[i]);
				update(cc, i, n, 1);
				i_++;
			}
			ans[h] += query(ss, r) - query(ss, l - 1)
				+ (query(cc, r) - query(cc, l - 1)) * l;
		}
	}
	void main() {
		int n = sc.nextInt();
		int q = sc.nextInt();
		ss = new long[n]; cc = new long[n];
		qu = new int[n]; pp = new int[n];
		ii = new Integer[n];
		for (int i = 0; i < n; i++)
			ii[i] = i;
		hh = new Integer[q];
		for (int h = 0; h < q; h++)
			hh[h] = h;
		int[] aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = sc.nextInt() - 1;
		int[] ll = new int[q];
		int[] rr = new int[q];
		for (int h = 0; h < q; h++)
			ll[h] = sc.nextInt() - 1;
		for (int h = 0; h < q; h++)
			rr[h] = sc.nextInt() - 1;
		long[] ans = new long[q];
		solve(aa, n, ll, rr, ans, q);
		for (int i = 0, j = n - 1; i < j; i++, j--) {
			int tmp = aa[i]; aa[i] = aa[j]; aa[j] = tmp;
		}
		for (int h = 0; h < q; h++) {
			int l = n - 1 - rr[h];
			int r = n - 1 - ll[h];
			ll[h] = l;
			rr[h] = r;
		}
		solve(aa, n, ll, rr, ans, q);
		for (int h = 0; h < q; h++)
			print((long) n * (rr[h] - ll[h] + 1) - ans[h] + " ");
		println();
	}
}