1438_E. Yurii Can Do Everything_10235
Yurii is sure he can do everything. Can he solve this task, though?

He has an array a consisting of n positive integers. Let's call a subarray a[l...r] good if the following conditions are simultaneously satisfied: 

  * l+1 ≤ r-1, i. e. the subarray has length at least 3; 
  * (a_l ⊕ a_r) = (a_{l+1}+a_{l+2}+…+a_{r-2}+a_{r-1}), where ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 



In other words, a subarray is good if the bitwise XOR of the two border elements is equal to the sum of the rest of the elements. 

Yurii wants to calculate the total number of good subarrays. What is it equal to?

An array c is a subarray of an array d if c can be obtained from d by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line contains a single integer n (3 ≤ n ≤ 2⋅ 10^5) — the length of a. 

The second line contains n integers a_1,a_2,…,a_n (1 ≤ a_i < 2^{30}) — elements of a. 

Output

Output a single integer — the number of good subarrays. 

Examples

Input


8
3 1 2 3 1 2 3 15


Output


6

Input


10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854


Output


2

Note

There are 6 good subarrays in the example: 

  * [3,1,2] (twice) because (3 ⊕ 2) = 1; 
  * [1,2,3] (twice) because (1 ⊕ 3) = 2; 
  * [2,3,1] because (2 ⊕ 1) = 3; 
  * [3,1,2,3,1,2,3,15] because (3 ⊕ 15) = (1+2+3+1+2+3). 
import java.io.BufferedOutputStream;
import java.io.Closeable;
import java.io.DataInputStream;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.TreeSet;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	static class TaskAdapter implements Runnable {
		@Override
		public void run() {
			long startTime = System.currentTimeMillis();
			InputStream inputStream = System.in;
			OutputStream outputStream = System.out;
			FastReader in = new FastReader(inputStream);
			Output out = new Output(outputStream);
			EYuriiCanDoEverything solver = new EYuriiCanDoEverything();
			solver.solve(1, in, out);
			out.close();
			System.err.println(System.currentTimeMillis()-startTime+"ms");
		}
	}

	public static void main(String[] args) throws Exception {
		Thread thread = new Thread(null, new TaskAdapter(), "", 1<<28);
		thread.start();
		thread.join();
	}

	static class EYuriiCanDoEverything {
		private final int iinf = 1_000_000_000;

		public EYuriiCanDoEverything() {
		}

		public void solve(int kase, InputReader in, Output pw) {
			int n = in.nextInt();
			long[] arr = in.nextLong(n);
			long[] psum = Utilities.psum(arr);
			TreeSet<Node> ts = new TreeSet<>();
			long ans = 0;
			for(int i = n-1; i>=0; i--) {
				for(var j: ts.headSet(new Node(arr[i]+psum[i+1]), true)) {
					if(j.ind>=i+2&&j.p-psum[i+1]==(j.a^arr[i])) {
						ans++;
					}
				}
				ts.add(new Node(arr[i], psum[i], i));
			}
			pw.println(ans);
		}

		class Node implements Comparable<Node> {
			long a;
			long p;
			long val;
			int ind;

			public Node(long a, long p, int ind) {
				this.a = a;
				this.p = p;
				this.ind = ind;
				val = p-a;
			}

			public Node(long val) {
				this.val = val;
				ind = iinf;
			}

			public int compareTo(Node o) {
				return val==o.val ? ind-o.ind : Long.compare(val, o.val);
			}

		}

	}

	static interface InputReader {
		int nextInt();

		long nextLong();

		default long[] nextLong(int n) {
			long[] ret = new long[n];
			for(int i = 0; i<n; i++) {
				ret[i] = nextLong();
			}
			return ret;
		}

	}

	static class Utilities {
		public static long[] psum(long[] arr) {
			long[] psum = new long[arr.length+1];
			System.arraycopy(arr, 0, psum, 1, arr.length);
			Arrays.parallelPrefix(psum, Long::sum);
			return psum;
		}

	}

	static class Output implements Closeable, Flushable {
		public StringBuilder sb;
		public OutputStream os;
		public int BUFFER_SIZE;
		public String lineSeparator;

		public Output(OutputStream os) {
			this(os, 1<<16);
		}

		public Output(OutputStream os, int bs) {
			BUFFER_SIZE = bs;
			sb = new StringBuilder(BUFFER_SIZE);
			this.os = new BufferedOutputStream(os, 1<<17);
			lineSeparator = System.lineSeparator();
		}

		public void println(long l) {
			println(String.valueOf(l));
		}

		public void println(String s) {
			sb.append(s);
			println();
		}

		public void println() {
			sb.append(lineSeparator);
		}

		private void flushToBuffer() {
			try {
				os.write(sb.toString().getBytes());
			}catch(IOException e) {
				e.printStackTrace();
			}
			sb = new StringBuilder(BUFFER_SIZE);
		}

		public void flush() {
			try {
				flushToBuffer();
				os.flush();
			}catch(IOException e) {
				e.printStackTrace();
			}
		}

		public void close() {
			flush();
			try {
				os.close();
			}catch(IOException e) {
				e.printStackTrace();
			}
		}

	}

	static class FastReader implements InputReader {
		final private int BUFFER_SIZE = 1<<16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer;
		private int bytesRead;

		public FastReader(InputStream is) {
			din = new DataInputStream(is);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public int nextInt() {
			int ret = 0;
			byte c = skipToDigit();
			boolean neg = (c=='-');
			if(neg) {
				c = read();
			}
			do {
				ret = ret*10+c-'0';
			} while((c = read())>='0'&&c<='9');
			if(neg) {
				return -ret;
			}
			return ret;
		}

		public long nextLong() {
			long ret = 0;
			byte c = skipToDigit();
			boolean neg = (c=='-');
			if(neg) {
				c = read();
			}
			do {
				ret = ret*10+c-'0';
			} while((c = read())>='0'&&c<='9');
			if(neg) {
				return -ret;
			}
			return ret;
		}

		private boolean isDigit(byte b) {
			return b>='0'&&b<='9';
		}

		private byte skipToDigit() {
			byte ret;
			while(!isDigit(ret = read())&&ret!='-') ;
			return ret;
		}

		private void fillBuffer() {
			try {
				bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			}catch(IOException e) {
				e.printStackTrace();
				throw new InputMismatchException();
			}
			if(bytesRead==-1) {
				buffer[0] = -1;
			}
		}

		private byte read() {
			if(bytesRead==-1) {
				throw new InputMismatchException();
			}else if(bufferPointer==bytesRead) {
				fillBuffer();
			}
			return buffer[bufferPointer++];
		}

	}
}


10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854
 8
3 1 2 3 1 2 3 15
 10
512647258 29130422 386945218 423464437 1022947864 244293674 452 216 953 822
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 216 953 822
 8
3 1 2 3 1 4 3 15
 8
3 1 2 2 1 4 3 15
 10
997230370 58052053 240970544 715275815 250707702 42457490 44100666 64791577 43523002 480196854
 8
3 1 2 3 1 1 3 15
 8
3 1 2 3 1 2 3 3
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 216 1463 822
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 192 1463 822
 8
3 1 2 2 1 4 3 1
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 192 1463 827
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 192 1463 1377
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 192 1463 865
 10
252370317 29130422 502029343 423464437 1022947864 244293674 452 192 1463 865
 10
252370317 5858001 502029343 423464437 1022947864 244293674 452 192 1463 865
 10
512647258 29130422 386945218 423464437 1022947864 244293674 452 216 953 533
 8
3 1 3 3 1 2 3 15
 10
252370317 29130422 386945218 423464437 1022947864 131754458 452 216 953 822
 8
3 1 2 3 1 4 3 3
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 216 1216 822
 8
3 1 2 2 1 4 3 11
 10
252370317 29130422 386945218 423464437 1022947864 428172364 452 192 1463 822
 8
3 2 2 2 1 4 3 1
 10
252370317 29130422 386945218 423464437 42655514 244293674 452 192 1463 827
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 18 1463 1377
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 192 1903 865
 10
252370317 29130422 502029343 423464437 1022947864 244293674 452 192 1731 865
 10
252370317 5858001 502029343 423464437 1022947864 244293674 452 368 1463 865
 10
997230370 58052053 240970544 212328839 250707702 42457490 44100666 64791577 43523002 480196854
 10
252370317 29130422 386945218 423464437 1022947864 131754458 452 312 953 822
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 216 1216 1436
 8
3 1 2 2 1 1 3 11
 10
252370317 29130422 386945218 423464437 1022947864 428172364 452 192 2715 822
 8
3 2 2 2 2 4 3 1
 10
252370317 1421655 386945218 423464437 42655514 244293674 452 192 1463 827
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 19 1463 1377
 10
252370317 29130422 386945218 423464437 1022947864 244293674 452 192 1903 73
 10
252370317 29130422 502029343 423464437 1022947864 244293674 848 192 1731 865
 10
252370317 5858001 502029343 423464437 1022947864 124929409 452 368 1463 865
 10
940720956 58052053 240970544 212328839 250707702 42457490 44100666 64791577 43523002 480196854
 10
252370317 29130422 386945218 423464437 1022947864 131754458 452 312 953 1642
 10
252370317 29130422 595315250 423464437 1022947864 244293674 452 216 1216 1436
 8
4 1 2 2 1 1 3 11
 10
252370317 29130422 169373979 423464437 1022947864 428172364 452 192 2715 822
 10
252370317 1173612 386945218 423464437 42655514 244293674 452 192 1463 827
 10
252370317 29130422 386945218 423464437 1022947864 244293674 194 19 1463 1377
 10
252370317 29130422 386945218 423650454 1022947864 244293674 452 192 1903 73
 10
252370317 29130422 502029343 432606513 1022947864 244293674 848 192 1731 865
 10
252370317 5858001 502029343 423464437 1022947864 124929409 452 368 1463 1683
 10
940720956 58052053 240970544 123076536 250707702 42457490 44100666 64791577 43523002 480196854
 10
252370317 10245853 386945218 423464437 1022947864 131754458 452 312 953 1642
 10
252370317 41562972 595315250 423464437 1022947864 244293674 452 216 1216 1436
 10
252370317 29130422 169373979 423464437 1022947864 428172364 318 192 2715 822
 10
252370317 1173612 386945218 423464437 42655514 244293674 452 192 1463 916
 10
252370317 29130422 386945218 423464437 606530482 244293674 194 19 1463 1377
 10
252370317 29130422 417763059 423650454 1022947864 244293674 452 192 1903 73
 10
252370317 29130422 502029343 22019231 1022947864 244293674 848 192 1731 865
 10
252370317 5858001 502029343 423464437 1022947864 124929409 452 368 1463 154
 10
940720956 58052053 240970544 123076536 250707702 42457490 44100666 64791577 51170082 480196854
 10
252370317 10245853 386945218 516648195 1022947864 131754458 452 312 953 1642
 10
252370317 41562972 595315250 423464437 1022947864 244293674 452 216 1216 1600
 10
252370317 29130422 169373979 423464437 1022947864 428172364 318 192 3396 822
 10
252370317 1173612 386945218 423464437 42655514 244293674 452 192 268 916
 10
252370317 49237220 386945218 423464437 606530482 244293674 194 19 1463 1377

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