#include <iostream>
using namespace std;
 
template<class T>
T sum_of_n (T n) {
  T total = 0;
  for (T i = 1; i <= n; ++i) total += i;
  return total;
}
 
unsigned int sum_of_n_formula(unsigned int n) {
	return (n >> (~n & 1))
	       * ((n + 1) >> (n & 1));
}
 
int main() {
	// no overflow
	cout << sum_of_n<unsigned int>(1000) << endl;
	cout << sum_of_n<int>(1000) << endl;
	cout << sum_of_n_formula(1000) << endl;
	// overflow
	cout << sum_of_n<unsigned int>(1000000000) << endl;
	cout << sum_of_n<int>(1000000000) << endl;
	cout << sum_of_n_formula(1000000000) << endl;
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdGVtcGxhdGU8Y2xhc3MgVD4KVCBzdW1fb2ZfbiAoVCBuKSB7CiAgVCB0b3RhbCA9IDA7CiAgZm9yIChUIGkgPSAxOyBpIDw9IG47ICsraSkgdG90YWwgKz0gaTsKICByZXR1cm4gdG90YWw7Cn0KCnVuc2lnbmVkIGludCBzdW1fb2Zfbl9mb3JtdWxhKHVuc2lnbmVkIGludCBuKSB7CglyZXR1cm4gKG4gPj4gKH5uICYgMSkpCgkgICAgICAgKiAoKG4gKyAxKSA+PiAobiAmIDEpKTsKfQoKaW50IG1haW4oKSB7CgkvLyBubyBvdmVyZmxvdwoJY291dCA8PCBzdW1fb2Zfbjx1bnNpZ25lZCBpbnQ+KDEwMDApIDw8IGVuZGw7Cgljb3V0IDw8IHN1bV9vZl9uPGludD4oMTAwMCkgPDwgZW5kbDsKCWNvdXQgPDwgc3VtX29mX25fZm9ybXVsYSgxMDAwKSA8PCBlbmRsOwoJLy8gb3ZlcmZsb3cKCWNvdXQgPDwgc3VtX29mX248dW5zaWduZWQgaW50PigxMDAwMDAwMDAwKSA8PCBlbmRsOwoJY291dCA8PCBzdW1fb2ZfbjxpbnQ+KDEwMDAwMDAwMDApIDw8IGVuZGw7Cgljb3V0IDw8IHN1bV9vZl9uX2Zvcm11bGEoMTAwMDAwMDAwMCkgPDwgZW5kbDsKCXJldHVybiAwOwp9